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

arXiv 2021年

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket Institute of Mathematical Science HBNI India Indian Institute of Technology Jodhpur India Indian Institute of Technology Hyderabad India Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Science HBNI India University of Bergen Norway

The practice of partitioning a region into areas to favor a particular candidate or a party in an election has been known to exist for the last two centuries. This practice is commonly known as gerrymandering. Recently, the problem has also attracted a lot of attention from complexity theory perspective. In particular, Cohen-Zemach et al. [AAMAS 2018] proposed a graph theoretic version of gerrymandering problem and initiated an algorithmic study around this, which was continued by Ito et al. [AAMAS 2019]. In this paper we continue this line of investigation and resolve an open problem in the literature, as well as move the algorithmic frontier forward by studying this problem in the realm of parameterized complexity. Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of gerrymandering when the input graph is a path. Next, we propose a generalization of the model studied in [AAMAS 2019], where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv : C → Z+ for each voter v ∈ V (G) representing the preference of the voter over the candidates, a distinguished candidate p ∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts the vertex set needs to be partitioned (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K2,n, a complete bipartite graphs with one side of size 2 and the other of size n) or a complete graph. This hardness result implies that we cannot hope to have an algorithm wit

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Balanced Independent and Dominating Sets on Colored Interval Graphs

arXiv

引用

arXiv 2020年

作者： Bhore, Sujoy Haunert, Jan-Henrik Klute, Fabian Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Geoinformation Group University of Bonn Bonn Germany Algorithms and Complexity Group TU Wien Vienna Austria

We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let G = (V, E) be a vertex-colored interval graph with a k-coloring γ : V → {1,..., k} for some k ∈ N. A subset of vertices S ⊆ V is called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the f-BIS problem we design two FPT algorithms, one parameterized by (f, k) for interval graphs and the other parameterized by the vertex cover number for general graphs. Moreover, for the optimization variant of 1-BIS on interval graphs, we show that a simple greedy approach achieves approximation ratio 2. Copyright © 2020, The Authors. All rights reserved.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Parameterized study of STEINER TREE on unit disk graphs

arXiv

引用

arXiv 2020年

作者： Bhore, Sujoy Carmi, Paz Kolay, Sudeshna Kolay, Sudeshna Algorithms and Complexity Group Tu Wien Vienna Austria Ben-Gurion University of the Negev Beersheba Israel Indian Institute of Technology Kharagpur

We study the STEINER TREE problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R. The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the STEINER TREE problem on unit disk graphs can be solved in nO(√t+k)time. We also show that the STEINER TREE problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2O(k)nO(1). In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [16]. We mention that the algorithmic results can be made to work for STEINER TREE on disk graphs with bounded aspect ratio. Finally, we prove that STEINER TREE on disk graphs parameterized by k is W[1]-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Hardness

来源：评论

学校读者我要写书评

暂无评论

Solving the Steiner Tree Problem with few Terminals

Solving the Steiner Tree Problem with few Terminals

引用

International Conference on Tools for Artificial Intelligence (ICTAI)

作者： Johannes K. Fichte Markus Hecher André Schidler Institute of Artificial Intelligence TU Dresden Dresden Germany University of Potsdam Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9781728192284

ISBN: (纸本)9781728185361

The Steiner tree problem is a well-known problem in network design, routing, and VLSI design. Given a graph, edge costs, and a set of dedicated vertices (terminals), the Steiner tree problem asks to output a sub-graph that connects all terminals at minimum cost. A state-of-the-art algorithm to solve the Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner algorithm. The algorithm builds a Steiner tree of the entire instance by systematically searching for smaller instances, based on subsets of the terminals, and combining Steiner trees for these smaller instances. The search heavily relies on a guiding heuristic function in order to prune the search space. However, to ensure correctness, this algorithm allows only for limited heuristic functions, namely, those that satisfy a so-called consistency condition. In this paper, we enhance the Dijkstra-Steiner algorithm and establish a revisited algorithm, called DS*. The DS* algorithm allows for arbitrary lower bounds as heuristics relaxing the previous condition on the heuristic function. Notably, we can now use linear programming based lower bounds. Further, we capture new requirements for a heuristic function in a condition, which we call admissibility. We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible heuristic function. We implement DS* and combine it with modern preprocessing, resulting in an open-source solver (DS*Solve). Finally, we compare its performance on standard benchmarks and observe a competitive behavior.

关键词： Steiner trees Heuristic algorithms Very large scale integration Tools Routing Standards Open source software

来源：评论

学校读者我要写书评

暂无评论

Extending partial 1-planar drawings

arXiv

引用

arXiv 2020年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Klute, Fabian Nöllenburg, Martin Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group Tu Wien Vienna Australia

Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple (G,H,H) consisting of a graph G, a connected subgraph H of G and a drawing H of H, and the task is to extend H into a drawing of G while maintaining some desired property of the drawing, such as planarity. In this paper we study the problem of extending partial 1-planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of IC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planar graphs as well as IC-planar graphs is NP-complete and the NP-completeness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomial-Time tractability. Here, we show that both problems are fixed-parameter tractable when parameterized by the number of edges missing from H, i.e., the edge deletion distance between H and G. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain H from G. Copyright © 2020, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs

arXiv

引用

arXiv 2021年

作者： Bhyravarapu, Sriram Hartmann, Tim A. Hoang, Hung P. Kalyanasundaram, Subrahmanyam Reddy, I. Vinod The Institute of Mathematical Sciences HBNI Chennai India CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria Department of Computer Science and Engineering IIT Hyderabad India Department of Electrical Engineering and Computer Science IIT Bhilai India

A conflict-free coloring of a graph G is a (partial) coloring of its vertices such that every vertex u has a neighbor whose assigned color is unique in the neighborhood of u. There are two variants of this coloring, one defined using the open neighborhood and one using the closed neighborhood. For both variants, we study the problem of deciding whether the conflict-free coloring of a given graph G is at most a given number k. In this work, we investigate the relation of clique-width and minimum number of colors needed (for both variants) and show that these parameters do not bound one another. Moreover, we consider specific graph classes, particularly graphs of bounded clique-width and types of intersection graphs, such as distance hereditary graphs, interval graphs and unit square and disk graphs. We also consider Kneser graphs and split graphs. We give (often tight) upper and lower bounds and determine the complexity of the decision problem on these graph classes, which improve some of the results from the literature. Particularly, we settle the number of colors needed for an interval graph to be conflict-free colored under the open neighborhood model, which was posed as an open problem. Copyright © 2021, The Authors. All rights reserved.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

A unifying framework for characterizing and computing width measures

arXiv

引用

arXiv 2021年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Jaffke, Lars Kwon, O-Joung Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria Department of Informatics University of Bergen Bergen Norway Department of Mathematics Incheon National University Incheon Korea Republic of Discrete Mathematics Group Institute for Basic Science Daejeon Korea Republic of

algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can compute every possible F-branchwidth, providing a unifying framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width *** Codes 68Q27 Copyright © 2021, The Authors. All rights reserved.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for queue layouts

arXiv

引用

arXiv 2020年

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Bruxelles Belgium Dipartimento di Ingegneria Università degli Studi di Perugia Perugia Italy

An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h. Copyright © 2020, The Authors. All rights reserved.

关键词： Queueing theory

来源：评论

学校读者我要写书评

暂无评论

On Erdős–Szekeres-Type Problems for k-convex Point Sets 1

引用

30th International Workshop on Combinatorial algorithms, IWOCA 2019

作者： Balko, Martin Bhore, Sujoy Martínez Sandoval, Leonardo Valtr, Pavel Department of Applied Mathematics Charles University Prague Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université Paris France

ISBN: (数字)9783030250058

ISBN: (纸本)9783030250041

We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning simple polygonization of S such that the intersection of any straight line with its interior consists of at most k connected components. We address several open problems about k-convex point sets. In particular, we extend the well-known Erdős–Szekeres Theorem by showing that, for every fixed k ∈ N, every set of n points in the plane in general position (with no three collinear points) contains a k-convex subset of size at least Ω(logk n). We also show that there are arbitrarily large 3-convex sets of n points in the plane in general position whose largest 1-convex subset has size O(log n). This gives a solution to a problem posed by Aichholzer et al.Â [2]. We prove that there is a constant c > 0 such that, for every n ∈ N, there is a set S of n points in the plane in general position such that every 2-convex polygon spanned by at least c · log n points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al.Â [2] upÂ to a multiplicative constant and answers another of their open problems. © 2019, Springer Nature Switzerland AG.

关键词： Geometry

来源：评论

学校读者我要写书评

暂无评论

Mixed Linear Layouts: complexity, Heuristics, and Experiments

arXiv

引用

arXiv 2019年

作者： de Col, Philipp Klute, Fabian Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

A k-page linear graph layout of a graph G = (V, E) draws all vertices along a line and each edge in one of k disjoint halfplanes called pages, which are bounded by . We consider two types of pages. In a stack page no two edges should cross and in a queue page no edge should be nested by another edge. A crossing (nesting) in a stack (queue) page is called a conflict. The algorithmic problem is twofold and requires to compute (i) a vertex ordering and (ii) a page assignment of the edges such that the resulting layout is either conflict-free or conflict-minimal. While linear layouts with only stack or only queue pages are well-studied, mixed s-stack q-queue layouts for s, q ≥ 1 have received less attention. We show NP-completeness results on the recognition problem of certain mixed linear layouts and present a new heuristic for minimizing conflicts. In a computational experiment for the case s, q = 1 we show that the new heuristic is an improvement over previous heuristics for linear layouts. Copyright © 2019, The Authors. All rights reserved.

关键词： Queueing theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：