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

Partitioning graph drawings and triangulated simple polygons into greedily routable regions

International Journal of Computational Geometry and Applications 2017年第1-2期27卷 121-158页

作者： Nöllenburg, Martin Prutkin, Roman Rutter, Ignaz Algorithms and Complexity Group TU Wien Vienna Austria Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe Germany Algorithms and Visualization WandI Technische Universiteit Eindhoven Eindhoven Netherlands

A greedily routable region (GRR) is a closed subset of ℝ2, in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. © 2017 World Scientific Publishing Company.

关键词： Decomposing graph drawings Greedy region decomposition Greedy routing in wireless sensor networks Increasing-chord drawings

来源：评论

学校读者我要写书评

暂无评论

Deterministic Constrained Multilinear Detection 48

Deterministic Constrained Multilinear Detection

引用

48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023

作者： Brand, Cornelius Korchemna, Viktoriia Skotnica, Michael Algorithms and Complexity Group TU Wien Austria Department of Applied Mathematics Charles University Prague Czech Republic

ISBN: (纸本)9783959772921

We extend the algebraic techniques of Brand and Pratt (ICALP’21) for deterministic detection of k-multilinear monomials in a given polynomial with non-negative coefficients to the more general situation of detecting colored k-multilinear monomials that satisfy additional constraints on the multiplicities of the colors appearing in them. Our techniques can be viewed as a characteristic-zero generalization of the algebraic tools developed by Guillemot and Sikora (MFCS’10) and Björklund, Kaski and Kowalik (STACS’13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS’14), and give new deterministic algorithms for generalizations of certain questions on colored directed spanning trees or bipartite planar matchings running in deterministic time O∗(4k), studied originally by Gutin, Reidl, Wahlström and Zehavi (J. Comp. Sys. Sci. 95,’18). Finally, we give improved randomized algorithms for intersecting three and four matroids of rank k in characteristic zero, improving the record bounds of Brand and Pratt (ICALP’21) from O∗(64k) and O∗(256k), respectively, to O∗(4k). © Cornelius Brand, Viktoriia Korchemna, and Michael Skotnica

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Twin-Width Meets Feedback Edges and Vertex Integrity 19

Twin-Width Meets Feedback Edges and Vertex Integrity

引用

19th International Symposium on Parameterized and Exact Computation, IPEC 2024

作者： Balabán, Jakub Ganian, Robert Rocton, Mathis Faculty of Informatics Masaryk University Brno Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959773539

The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: An asymptotically tight bound between twin-width and the feedback edge number;A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency;An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph. © Jakub Balabán, Robert Ganian, and Mathis Rocton.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A SAT Attack on Rota’s Basis Conjecture 25

A SAT Attack on Rota’s Basis Conjecture

引用

25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022

作者： Kirchweger, Markus Scheucher, Manfred Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Institut für Mathematik Technische Universität Berlin Germany

ISBN: (纸本)9783959772426

The SAT modulo Symmetries (SMS) is a recently introduced framework for dynamic symmetry breaking in SAT instances. It combines a CDCL SAT solver with an external lexicographic minimality checking algorithm. We extend SMS from graphs to matroids and use it to progress on Rota’s Basis Conjecture (1989), which states that one can always decompose a collection of r disjoint bases of a rank r matroid into r disjoint rainbow bases. Through SMS, we establish that the conjecture holds for all matroids of rank 4 and certain special cases of matroids of rank 5. Furthermore, we extend SMS with the facility to produce DRAT proofs. External tools can then be used to verify the validity of additional axioms produced by the lexicographic minimality check. As a byproduct, we have utilized our framework to enumerate matroids modulo isomorphism and to support the investigation of various other problems on matroids. © Markus Kirchweger, Manfred Scheucher, and Stefan Szeider.

关键词： Combinatorial mathematics

来源：评论

学校读者我要写书评

暂无评论

On existential MSO and its relation to ETH 41

On existential MSO and its relation to ETH

引用

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Ganian, Robert De Haan, Ronald Kanj, Iyad Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria School of Computing DePaul University ChicagoIL United States

ISBN: (纸本)9783959770163

Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to k-CNF-Sat modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this paper, we extend the framework of Impagliazzo et al., and identify a larger set of problems that are equivalent to k- CNF-Sat modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second order logic whose expressions have a linear measure in terms of a complexity parameter, which is usually the universe size of the problem. This research direction can be traced back to Fagin's celebrated theorem stating that NP coincides with the class of problems expressible in existential second order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential monadic second order logic. The proposed class Linear Monadic NP is then the restriction of Monadic NP to problems whose expressions have linear measure in the complexity parameter. We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that Feedback Vertex Set is inexpressible in existential monadic second order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between Feedback Vertex Set (and variants of it) and 3-CNF-Sat. © Cody Geary

关键词： Computer circuits

来源：评论

学校读者我要写书评

暂无评论

Hedonic Diversity Games: A complexity Picture with More than Two Colors 36

Hedonic Diversity Games: A Complexity Picture with More than...

引用

36th AAAI Conference on Artificial Intelligence, AAAI 2022

作者： Ganian, Robert Hamm, Thekla Knop, Dušan Schierreich, Šimon Suchý, Ondřej Algorithms and Complexity Group TU Wien Austria Faculty of Information Technology Czech Technical University Prague Czech Republic

ISBN: (纸本)1577358767

Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a complete parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general Hedonic diversity games where the number of colors is not necessarily restricted to two, and show that-apart from two trivial cases-a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question posed in previous work. © 2022, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Towards a polynomial kernel for directed feedback vertex set 42

Towards a polynomial kernel for directed feedback vertex set

引用

42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017

作者： Bergougnoux, Benjamin Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Ramanujan, M.S. Université Clermont Auvergne LIMOS CNRS Aubière France Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770460

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008];since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus. © Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan;licensed under Creative Commons License CC-BY.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds 21

Worbel: Aggregating Point Labels into Word Clouds

引用

29th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2021

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal Bhopal India Algorithms and Complexity Group Tu Wien Vienna Austria

ISBN: (纸本)9781450386647

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021 ACM.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

SAT-Based Generation of Planar Graphs 26

SAT-Based Generation of Planar Graphs

引用

26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023

作者： Markus Kirchweger Manfred Scheucher Stefan Szeider Algorithms and Complexity Group TU Wien Austria Institut för Mathematik Technische Universität Berlin Germany

ISBN: (纸本)9783959772860

To test a graph's planarity in SAT-based graph generation we develop SAT encodings with dynamic symmetry breaking as facilitated in the SAT modulo Symmetry (SMS) framework. We implement and compare encodings based on three planarity criteria. In particular, we consider two eager encodings utilizing order-based and universal-set-based planarity criteria, and a lazy encoding based on Kuratowski's theorem. The performance and scalability of these encodings are compared on two prominent problems from combinatorics: The computation of planar Turán numbers and the Earth-Moon problem. We further showcase the power of SMS equipped with a planarity encoding by verifying and extending several integer sequences from the Online Encyclopedia of Integer Sequences (OEIS) related to planar graph enumeration. Furthermore, we extend the SMS framework to directed graphs which might be of independent interest. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Moon

来源：评论

学校读者我要写书评

暂无评论

Extending partial 1-planar drawings 47

Extending partial 1-planar drawings

引用

47th International Colloquium on Automata, Languages, and Programming, ICALP 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 Austria

ISBN: (纸本)9783959771382

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. © Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg;licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：