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

28th International Conference on Principles and Practice of Constraint Programming, CP 2022

作者： Dreier, Jan Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group University of Leeds United Kingdom

ISBN: (纸本)9783959772402

The constraint satisfaction problem (CSP) is among the most studied computational problems. While NP-hard, many tractable subproblems have been identified (Bulatov 2017, Zuk 2017). Backdoors, introduced by Williams, Gomes, and Selman (2003), gradually extend such a tractable class to all CSP instances of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a CSP instance and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021) for SAT, is a more refined distance measure, which admits the parallel utilization of different backdoor variables. Bounded backdoor size implies bounded backdoor depth, but there are instances of constant backdoor depth and arbitrarily large backdoor size. Dreier, Ordyniak, and Szeider (2022) provided fixed-parameter algorithms for finding backdoors of small depth into the classes of Horn and Krom formulas. In this paper, we consider backdoor depth for CSP. We consider backdoors w.r.t. tractable subproblems CΓ of the CSP defined by a constraint language Γ, i.e., where all the constraints use relations from the language Γ. Building upon Dreier et al.’s game-theoretic approach and their notion of separator obstructions, we show that for any finite, tractable, semi-conservative constraint language Γ, the CSP is fixed-parameter tractable parameterized by the backdoor depth into CΓ plus the domain size. With backdoors of low depth, we reach classes of instances that require backdoors of arbitrary large size. Hence, our results strictly generalize several known results for CSP that are based on backdoor size. © Jan Dreier, Sebastian Ordyniak, and Stefan Szeider.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

A Tight Subexponential-Time Algorithm for Two-Page Book Embedding 51

A Tight Subexponential-Time Algorithm for Two-Page Book Embe...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Ganian, Robert Müller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz Algorithms and Complexity Group TU Wien Austria School of Computing University of Leeds United Kingdom

ISBN: (纸本)9783959773225

A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into "pages", which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2O(√n) algorithm for computing a book embedding of an n-vertex graph on two pages – a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem. © Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani, and Mateusz Rychlicki.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Boundary Labeling in a Circular Orbit 32

Boundary Labeling in a Circular Orbit

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Bonerath, Annika Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Wulms, Jules University of Bonn Germany Algorithms and Complexity Group TU Wien Austria TU Eindhoven Netherlands Chair for Efficient Algorithms TU Munich Germany

ISBN: (纸本)9783959773430

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights. © Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Transitions in Dynamic Point Labeling 12

Transitions in Dynamic Point Labeling

引用

12th International Conference on Geographic Information Science, GIScience 2023

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Austria Algorithm Engineering Group TU Dortmund Germany

ISBN: (纸本)9783959772884

The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a dynamic setting, the set of point features and their corresponding labels change, and the labeling has to adapt to such changes. To aid the user in tracking these changes, we can use morphs, here called transitions, to indicate how a labeling changes. Such transitions have not gained much attention yet, and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions. When each label has a (non-negative) weight associated to it, and each overlap imposes a penalty proportional to the weight of the overlapping labels, we show that it is NP-complete to decide whether the penalty during a simultaneous transition has weight at most k. Finally, in a case study, we consider geotagged Twitter data on a map, by labeling points with rectangular labels showing tweets. We developed a prototype implementation to evaluate different transition styles in practice, measuring both number of overlaps and transition duration. © Thomas Depian, Guangping Li, Martin Nöllenburg, and Jules Wulms.

关键词： Information retrieval

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Slim Tree-Cut Width 17

Slim Tree-Cut Width

引用

17th International Symposium on Parameterized and Exact Computation, IPEC 2022

作者： Ganian, Robert Korchemna, Viktoriia Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772600

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as an approximation algorithm for computing the parameter. © Robert Ganian and Viktoriia Korchemna.

关键词： Structural properties

来源：评论

学校读者我要写书评

暂无评论

A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)

A Mathematical Runtime Analysis of the Non-dominated Sorting...

引用

2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion

作者： Wietheger, Simon Doerr, Benjamin Algorithms and Complexity Group TU Wien Vienna Austria École Polytechnique CNRS Institut Polytechnique de Paris Palaiseau France

ISBN: (纸本)9798400704956

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that it is less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving that the NGSA-II for an exponential number of iterations misses a constant factor of the Pareto front of the simple m-objective OneMinMax problem when m ≥ *** this work, we provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives. We prove that the NSGA-III with sufficiently many reference points - a small constant factor more than the size of the Pareto front, as suggested for this algorithm - computes the complete Pareto front of the 3-objective OneMinMax benchmark in an expected number of O(n log n) iterations. This result holds for all population sizes (that are at least the size of the Pareto front). It shows a drastic advantage of the NSGA-III over the NSGA-II on this *** paper for the Hot-off-the-Press track at GECCO 2024 summarizes the work Simon Wietheger and Benjamin Doerr. A mathematical runtime analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2023. 5657 - 5665, 2023. [15]. © 2024 Copyright held by the owner/author(s).

关键词： Genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Splitting Plane Graphs to Outerplanarity

引用

Journal of Graph algorithms and Applications 2024年第3期28卷 31-48页

作者： Gronemann, Martin Nöllenburg, Martin Villedieu, Anaïs Algorithms and Complexity Group TU Wien Vienna Austria

Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired properties with as few splits as possible, most often planarity, for which the problem is NP-hard. Here we study how to minimize the number of splits to turn a plane graph into an outerplane one. We tackle this problem by establishing a direct connection between splitting a plane graph to outerplanarity, finding a connected face cover, and finding a feedback vertex set in its dual. We prove NP-completeness for plane biconnected graphs, while we show that a polynomial-time algorithm exists for maximal planar graphs. Additionally, we show upper and lower bounds for certain families of maximal planar graphs. Finally, we provide a SAT formulation for the problem, and evaluate it on a small benchmark. © 2024, Brown University. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Fixed-Parameter algorithms for Computing Bend-Restricted RAC Drawings of Graphs

引用

Journal of Graph algorithms and Applications 2024年第2期28卷 131-150页

作者： Brand, Cornelius Ganian, Robert Röder, Sebastian Schager, Florian Algorithms and Complexity Group TU Wien Vienna Austria

In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly 90◦, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research and particular attention has been paid to RAC drawings with at most 0, 1, 2 and 3 bends per edge, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of bend-restricted RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph G with at most b bends where each edge e has a prescribed upper-bound 0 ≤ β(e) ≤ 3 on the number of bends it can support (or determining that none exists) is: • fixed-parameter tractable parameterized by the feedback edge number of G, and • fixed-parameter tractable parameterized by b plus the vertex cover number of G. © 2024, Brown University. All rights reserved.

关键词： Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Hive Plots: A Combinatorial Framework

引用

Journal of Graph algorithms and Applications 2024年第2期28卷 101-129页

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

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot;(2) optimize the cyclic axis order to bring more strongly connected groups near each other;(3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable exact and heuristic algorithmic approaches, implement them as an instantiation of our framework, and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding the algorithmic choices of our framework. The code of the implementation and a prototype web application can be found on OSF1. © 2024, Brown University. All rights reserved.

关键词： Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：