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

arXiv 2019年

作者： Ganian, Robert Lodha, Neha Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria Algorithms Group University of Sheffield Sheffield United Kingdom

The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided;the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters treecut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms. Our approach for computing treecut width and treedepth decompositions is based on efficient encodings of these decomposition methods to the propositional satisfiability problem (SAT). Once an encoding is generated, any satisfiability solver can be used to find the decomposition. This allows us to leverage the surprising power of todays state-of-the art SAT solvers. The success of SAT-based decomposition methods crucially depends on the used characterisation of the decomposition method, as not every characterisation is suitable for that task. For instance, the successful leading SAT encoding for treewidth is based on a characterisation of treewidth in terms of elimination orderings. For treecut w

关键词： Signal encoding

来源：评论

学校读者我要写书评

暂无评论

Balanced Connected Subgraph Problem in Geometric Intersection Graphs 1

引用

13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

作者： Bhore, Sujoy Jana, Satyabrata Pandit, Supantha Roy, Sasanka Algorithms and Complexity Group TU Wien Vienna Austria Indian Statistical Institute Kolkata India Dhirubhai Ambani Institute of Information and Communication Technology GandhinagarGujarat India

ISBN: (数字)9783030364120

ISBN: (纸本)9783030364113

We study the (shortly,) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given agraph, where each vertex in V is colored with either "" or "", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is, i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for theproblem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs. © 2019, Springer Nature Switzerland AG.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

A join-based hybrid parameter for constraint satisfaction

arXiv

引用

arXiv 2019年

作者： Ganian, Robert Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria Algorithms Group University of Sheffield Sheffield United Kingdom

We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances. Copyright © 2019, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Untangling Circular Drawings: algorithms and complexity

arXiv

引用

arXiv 2021年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria University of Passau Passau Germany Research Unit of Computer Graphics TU Wien Vienna Austria St. Pölten University of Applied Sciences St. Pölten Austria

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift◦(δG) ≤ n − ⌊√n − 2⌋ − 2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. For this problem, we provide a tight upper bound shift◦(δG) ≤ ⌊n/2⌋ − 1 and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © 2021, CC BY.

关键词： Drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

Minimizing crossings in constrained two-sided circular graph layouts 34

Minimizing crossings in constrained two-sided circular graph...

引用

34th International Symposium on Computational Geometry, SoCG 2018

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

ISBN: (纸本)9783959770668

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k > 1, extending the previously studied case k = 0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k = 1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k = 1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm. © Fabian Klute and Martin Nöllenburg;licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

关键词： Drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

Extending Nearly Complete 1-Planar Drawings in Polynomial Time

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 Austria Deptartment of Information and Computing Sciences Utrecht University Netherlands

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when H can be obtained from G by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision *** Codes 68R10 Copyright © 2020, The Authors. All rights reserved.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Finding large matchings in 1-planar graphs of minimum degree 3

arXiv

引用

arXiv 2020年

作者： Biedl, Therese Klute, Fabian David R. Cheriton School of Computer Science University of Waterloo WaterlooONN2L 1A2 Canada Algorithms and Complexity Group TU Wien Austria

A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least n+12/7 , and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a general-purpose maximum-matching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least n+12/7 in a 1-planar graph with minimum degree 3. Copyright © 2020, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

2.5-connectivity: Unique components, critical graphs, and applications

arXiv

引用

arXiv 2020年

作者： Heinrich, Irene Heller, Till Schmidt, Eva Streicher, Manuel Algorithms and Complexity Group Department of Computer Science Technische Universität Kaiserslautern Kaiserslautern Germany Department of Optimization Fraunhofer ITWM Kaiserslautern Germany Optimization Research Group Department of Mathematics Technische Universität Kaiserslautern Kaiserslautern Germany

If a 2-connected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every 2-connected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a treestructure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle *** Codes 05C40, 05C45, 05C85, 05C75 Copyright © 2020, The Authors. All rights reserved.

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploring semi-automatic map labeling

arXiv

引用

arXiv 2019年

作者： Klute, Fabian Li, Guangping Löffler, Raphael Nöllenburg, Martin Schmidt, Manuela Algorithms and Complexity Group TU Wien Vienna Austria Research Group Cartography TU Wien Vienna Austria

Label placement in maps is a very challenging task that is critical for the overall map quality. Most previous work focused on designing and implementing fully automatic solutions, but the resulting visual and aesthetic quality has not reached the same level of sophistication that skilled human cartographers achieve. We investigate a different strategy that combines the strengths of humans and algorithms. In our proposed method, first an initial labeling is computed that has many well-placed labels but is not claiming to be perfect. Instead it serves as a starting point for an expert user who can then interactively and locally modify the labeling where necessary. In an iterative human-in-the-loop process alternating between user modifications and local algorithmic updates and refinements the labeling can be tuned to the user's needs. We demonstrate our approach by performing different possible modification steps in a sample workflow with a prototypical interactive labeling editor. Further, we report computational performance results from a simulation experiment in QGIS, which investigates the differences between exact and heuristic algorithms for semi-automatic map labeling. To that end, we compare several alternatives for recomputing the labeling after local modifications and updates, as a major ingredient for an interactive labeling editor. Copyright © 2019, The Authors. All rights reserved.

关键词： Heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Geometric systems of unbiased representatives 31

Geometric systems of unbiased representatives

引用

31st Canadian Conference on Computational Geometry, CCCG 2019

作者： Banik, Aritra Bhattacharya, Bhaswar B. Bhore, Sujoy Martínez-Sandoval, Leonardo National Institute of Science Education and Research School of Computer Sciences HBNI Bhubaneswar India Department of Statistics University of Pennsylvania Philadelphia United States Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université France

Let P be a set of points in Rd, B a bicoloring of P and O a family of geometric objects (that is, intervals, boxes, balls, etc). An object from O is called balanced with respect to B if it contains the same number of points from each color of B. For a collection B of bicolorings of P, a geometric system of unbiased representatives (GSUR) is a subset such that for any bicoloring B of β there is an object in O0 that is balanced with respect to B. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives. © CCCG 2019. All rights reserved.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：