检索结果-内蒙古大学图书馆

48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Arrighi, Emmanuel Gruttemeier, Niels Morawietz, Nils Sommer, Frank Wolf, Petra Univ Bergen Bergen Norway Philipps Univ Marburg Marburg Germany

ISBN: (纸本)9783031231001;9783031231018

We study the computational complexity of determining structural properties of edge-periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge e of the graph, a binary string se determines in which time steps the edge is present, namely e is present in time step t if and only if se contains a 1 at position t mod vertical bar s(e)vertical bar. Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the new concept of EPGs such as is there a time step or a sliding window of size Delta in which the graph (1) is minor-free;(2) contains a minor;(3) is subgraph-free;(4) contains a subgraph;with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several algorithms.

关键词： Temporal graphs Minor-free Minor containment Subgraph-free Subgraph containment parameterized complexity FPT-algorithm

来源：评论

学校读者我要写书评

暂无评论

The Parametrized complexity of the Segment Number 31st

The Parametrized Complexity of the Segment Number

引用

31st International Symposium on Graph Drawing and Network Visualization (GD)

作者： Cornelsen, Sabine Da Lozzo, Giordano Grilli, Luca Gupta, Siddharth Kratochvil, Jan Wolff, Alexander Univ Konstanz Constance Germany Roma Tre Univ Rome Italy Univ Perugia Perugia Italy Univ Warwick Coventry W Midlands England Charles Univ Prague Prague Czech Republic Univ Wurzburg Wurzburg Germany

ISBN: (纸本)9783031492747;9783031492754

Given a straight-line drawing of a graph, a segment is a maximal set of edges that form a line segment. Given a planar graph G, the segment number of G is the minimum number of segments that can be achieved by any planar straight-line drawing of G. The line cover number of G is the minimum number of lines that support all the edges of a planar straight-line drawing of G. Computing the segment number or the line cover number of a planar graph is there exists R-complete and, thus, NP-hard. We study the problem of computing the segment number from the perspective of parameterized complexity. We show that this problem is fixed-parameter tractable with respect to each of the following parameters: the vertex cover number, the segment number, and the line cover number. We also consider colored versions of the segment and the line cover number.

关键词： Segment number Line cover number Vertex cover number parameterized complexity Visual complexity

来源：评论

学校读者我要写书评

暂无评论

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

Solving Distance-constrained Labeling Problems for Small Dia...

引用

37th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Hanaka, Tesshu Ono, Hirotaka Sugiyama, Kosuke Kylishu Univ Dept Informat Fukuoka Japan Nagoya Univ Dept Math Informat Nagoya Aichi Japan

ISBN: (纸本)9798350311990

For an undirected graph G = (V, E) and a k-non-negative integer vector p = (p(1),..., p(k)), a mapping l : V -> N boolean OR {0} is called an L(p)-labeling of G if |vertical bar l(u) - l(v)vertical bar >= p(d) for any two distinct vertices u, v is an element of V with distance d, and the maximum value of {l(v) vertical bar v is an element of V} is called the span of l. Originally, L(p)-labeling of G for p = (2, 1) is introduced in the context of frequency assignment in radio networks, where 'close' transmitters must receive different frequencies and 'very close' transmitters must receive frequencies that are at least two frequencies apart so that they can avoid interference. L(p)-LABELING is the problem of finding the minimum span lambda(p) among L(p)-labelings of G, which is NP-hard for every non-zero p. L(p)-LABELING is well studied for specific p's;in particular, many (exact or approximation) algorithms for general graphs or restricted classes of graphs are proposed for p = (2, 1) or more generally p = (p, q). Unfortunately, most algorithms strongly depend on the values of p, and it is not apparent to extend algorithms for p to ones for another p ' in general. In this paper, we give a simple polynomial-time reduction of L(p)-LABELING on graphs with a small diameter to METRIC ( PATH) TSP, which enables us to use numerous results on (METRIC) TSP. On the practical side, we can utilize various high-performance heuristics for TSP, such as Concordo and LKH, to solve our problem. On the theoretical side, we can see that the problem for any p under this framework is 1.5-approximable, and it can be solved by the Held-Karp algorithm in O(2(n)n(2)) time, where n is the number of vertices, and so on.

关键词： Frequency Assignment Distance-constrained Labeling L(p(1),...p(k))-Labeling TSP Graph Diameter parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Upward and Orthogonal Planarity are W-Hard parameterized by Treewidth 31st

Upward and Orthogonal Planarity are W-Hard Parameterized by ...

引用

31st International Symposium on Graph Drawing and Network Visualization (GD)

作者： Jansen, Bart M. P. Khazaliya, Liana Kindermann, Philipp Liotta, Giuseppe Montecchiani, Fabrizio Simonov, Kirill Eindhoven Univ Technol Eindhoven Netherlands Tech Univ Wien Vienna Austria Univ Trier Trier Germany Univ Perugia Perugia Italy Univ Potsdam Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9783031492747;9783031492754

UPWARD PLANARITY TESTING and RECTILINEAR PLANARITY TESTING are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known n(O(tw))-time algorithms cannot be improved to run in time n(o(tw)) unless ETH fails.

关键词： Upward Planarity Rectilinear Planarity parameterized complexity Treewidth

来源：评论

学校读者我要写书评

暂无评论

Polynomial Formal Verification exploiting Constant Cutwidth 34

Polynomial Formal Verification exploiting Constant Cutwidth

引用

34th International Workshop on Rapid System Prototyping - Shortening the Path from Specification to Prototype

作者： Nadeem, Mohamed Kleinekathoefer, Jan Drechsler, Rolf Univ Bremen Bremen Germany DFKI GmbH Bremen Germany

ISBN: (纸本)9798400704109

Only formal methods can guarantee the correctness of a circuit, but are usually very time and memory consuming. Therefore, efficient formal verification is key in the design of complex circuits. Many verification techniques have been introduced, which mostly fail to give bounds for the time complexity of the verification process. To overcome this issue, Polynomial Formal Verification (PFV) was introduced. This paper introduces a novel approach to PFV of circuits, by leveraging the concept of constant cutwidth. We divide the circuit into subgraphs, one for every output. This makes the verification of every subgraph only dependent on the cutwidth of the circuit and independent of the bitwidth. One main problem we solve is the passing of information between those subgraphs. The approach enables formal verification in linear time for circuits with constant cutwidth. As many different types of adders have a constant cutwidth, we can prove that those are verifiable in linear time. Those theoretical findings are backed by experiments including different adder architectures with up to 10k bit wide inputs.

关键词： Polynomial Formal Verification Logic Synthesis parameterized complexity Answer Set Programming Model-Based Reasoning

来源：评论

学校读者我要写书评

暂无评论

Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves 24th

Kernelization for Finding Lineal Topologies (Depth-First Spa...

引用

24th International Symposium on Fundamentals of Computation Theory (FCT)

作者： Sam, Emmanuel Bergougnoux, Benjamin Golovach, Petr A. Blaser, Nello Univ Bergen Dept Informat Bergen Norway Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9783031435867;9783031435874

For a given graph G, a depth-first search (DFS) tree T of G is an r-rooted spanning tree such that every edge of G is either an edge of T or is between a descendant and an ancestor in T. A graph G together with a DFS tree is called a lineal topology T = (G, r, T). Sam et al. (2023) initiated study of the parameterized complexity of the MIN-LLT and MAX-LLT problems which ask, given a graph G and an integer k >= 0, whether G has a DFS tree with at most k and at least k leaves, respectively. Particularly, they showed that for the dual parameterization, where the tasks are to find DFS trees with at least n- k and at most n - k leaves, respectively, these problems are fixed-parameter tractable when parameterized by k. However, the proofs were based on Courcelle's theorem, thereby making the running times a tower of exponentials. We prove that both problems admit polynomial kernels with O(k(3)) vertices. In particular, this implies FPT algorithms running in k(O(k))center dot n(O(1)) time. We achieve these results by making use of a O(k)-sized vertex cover structure associated with each problem. This also allows us to demonstrate polynomial kernels for MIN-LLT and MAX-LLT for the structural parameterization by the vertex cover number.

关键词： DFS Tree Spanning Tree Kernelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Treewidth-based algorithms for the small parsimony problem on networks

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2022年第1期17卷 1-31页

作者： Scornavacca, Celine Weller, Mathias Univ Montpellier CNRS IRD ISEMEPHE Montpellier France Univ Gustave Eiffel CNRS LIGM Paris France

Background: Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the SMALL PARSIMONY problem: given a tree T and an assignment of character-states to its leaves, assign states to the internal nodes of Tsuch as to minimize the parsimony score, that is, the number of edges of Tconnecting nodes with different states. While this problem is polynomial-time solvable on trees, the matter is more complicated if T contains reticulate events such as hybridizations or recombinations, i.e. when T is a network. Indeed, three different versions of the parsimony score on networks have been proposed and each of them is NP-hard to decide. Existing parameterized algorithms focus on combining the number c of possible character-states with the number of reticulate events (per biconnected component). Results: We consider the parameter treewidth t of the underlying undirected graph of the input network, presenting dynamic programming algorithms for (slight generalizations of) all three versions of the parsimony problem on size-n networks running in times c(t)n(O(1)), (3c)(t)n(O(1)), and 6(tc)n(O(1)) respectively. Our algorithms use a formulation of the treewidth that may facilitate formalizing tree-width-based dynamic programming algorithms on phylogenetic networks for other problems. Conclusions: Our algorithms allow the computation of the three popular parsimony scores, modeling the evolutionary development of a (multistate) character on a given phylogenetic network of low treewidth. Our results subsume and improve previously known algorithm for all three variants. While our results rely on being given a "good"tree-decomposition of the input, encouraging theoretical results as well as practical implementations producing them are publicly available. We present a reformulation of tree decompositions in terms of"agreeing trees" on the same set of nodes. As this formulation may come

关键词： Phylogenetics Parsimony Phylogenetic networks parameterized complexity Dynamic programming Treewidth

来源：评论

学校读者我要写书评

暂无评论

A Fine-grained View on Stable Many-to-one Matching Problems with Lower and Upper Quotas

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2022年第2期10卷 1-53页

作者： Boehmer, Niclas Heeger, Klaus Tech Univ Berlin Algorithm & Computat Complex Ernst Reuter Pl 7 D-10587 Berlin Germany

In the NP-hard Hospital Residents problem with lower and upper quotas (HR-QUL), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero. We analyze this problem from a parameterized complexity perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, answering an open question of Biro et al. [TCS 2010], we present an involved polynomial-time algorithm that finds a stable matching (if it exists) on instances with maximum lower quota two. Alongside HR-QUL, we also consider two closely related models of independent interest, namely, the special case of HR-QUL where each hospital has only a lower quota but no upper quota and the variation of HR-QUL where hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas. Last, we investigate the parameterized complexity of these three NP-hard problems when preferences may contain ties.

关键词： Hospital Residents problem stable matching House Allocation problem parameterized complexity lower and upper quotas

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of the bipartizing matching problem

引用

ANNALS OF OPERATIONS RESEARCH 2022年第2期316卷 1235-1256页

作者： Lima, Carlos V. G. C. Rautenbach, Dieter Souza, Ueverton S. Szwarcfiter, Jayme L. Univ Fed Cariri Ctr Ciencias & Tecnol Juazeiro Do Norte Brazil Ulm Univ Inst Optimizat & Operat Res Ulm Germany Univ Fed Fluminense Inst Comp Niteroi RJ Brazil Univ Fed Rio de Janeiro COPPE PESC Rio De Janeiro Brazil

Given a graph G = ( V, E), an edge bipartization set of G is a subset E' subset of E(G) such that G' = (V, E\E') is bipartite. An edge bipartization set that is also a matching of G is called a bipartizingmatching of G. Let BM be the family of all graphs admitting a bipartizing matching. Although every graph has an edge bipartization set, the problem of recognizing graphs G having bipartizing matchings (G is an element of BM) is challenging. A (k, d)-coloring of a graph G is a k-coloring of V( G) such that each vertex of G has at most d neighbors with the same color as itself. Clearly a (k, 0)-coloring is a proper vertex k-coloring of G and, for any d > 0, the k-coloring is non-proper, also known as defective. A graph belongs toBM if and only if it admits a (2, 1)-coloring. Lovasz (1966) proved that for any integer k > 0, any graph of maximum degree Delta admits a (k, left perpendicular Delta/kright perpendicular)-coloring. In this paper, we show that it is NP-complete to determine whether a 3-colorable planar graph of maximum degree 4 belongs to BM, i.e., (2, 1)-colorable. Besides, we show that it is NP-complete to determine whether planar graphs of maximum degree 6 or 8 admit a (2, 2) or (2, 3)-coloring, respectively. Due to Lovasz (1966), our results are tight in the sense that on graphs with maximum degree three, five, and seven, there always exists a (2, 1), (2, 2), and (2, 3)-coloring, respectively. Finally, we present polynomial-time algorithms for particular graph classes, besides some remarks on the parameterized complexity of the problem of recognizing graphs in BM.

关键词： Graph modification problems Edge bipartization Defective coloring Planar graphs NP-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Offensive alliances in graphs

引用

THEORETICAL COMPUTER SCIENCE 2024年 989卷

作者： Gaikwad, Ajinkya Maity, Soumen Indian Inst Sci Educ & Res Dept Math Dr Homi Bhabha Rd Pune 411008 Maharashtra India

The OFFENSIVE ALLIANCE problem has been studied extensively during the last twenty years. A set S subset of V of vertices is an offensive alliance in an undirected graph G = (V, E) if each v is an element of N(S) has at least as many neighbors in S as it has neighbors (including itself) not in S. We study the classical and parameterized complexity of the OFFENSIVE ALLIANCE problem, where the aim is to find a minimum size offensive alliance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph;this puts it among the few problems that are FPT when parameterized by solution size but not when parameterized by treewidth (unless FPT=W[1]), (2) the problem cannot be solved in time O*(2 degrees((k log k))) where k is the solution size, unless ETH fails, (3) it does not admit a polynomial kernel parameterized by solution size and vertex cover of the input graph. On the positive side we prove that (4) it can be solved in time O*(VC(G)(O(VC(G)))) where VC(G) is the vertex cover number of the input graph. (5) it admits an FPT algorithm when parameterized by vertex integrity of input graph. In terms of classical complexity, we prove that (6) the problem cannot be solved in time 2 degrees((n)) even when restricted to bipartite graphs, unless ETH fails, (7) it cannot be solved in time 2 degrees((root n)) even when restricted to apex graphs, unless ETH fails. We also prove that (8) it is NP-complete even when restricted to bipartite, chordal, split and circle graphs.

关键词： Defensive and offensive alliance parameterized complexity FPT W[1]-hard Treewidth ETH

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：