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

Block Crossings in One-Sided Tanglegrams

学校读者我要写书评

暂无评论

arXiv 2023年

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

Tanglegrams are drawings of two rooted binary phylogenetic trees and a matching between their leaf sets. The trees are drawn crossing-free on opposite sides with their leaf sets facing each other on two vertical lines. Instead of minimizing the number of pairwise edge crossings, we consider the problem of minimizing the number of block crossings, that is, two bundles of lines crossing each other locally. With one tree fixed, the leaves of the second tree can be permuted according to its tree structure. We give a complete picture of the algorithmic complexity of minimizing block crossings in one-sided tanglegrams by showing NP-completeness, constant-factor approximations, and a fixed-parameter algorithm. We also state first results for non-binary trees. © 2023, CC BY.

关键词： Binary trees

Generating Streamlining Constraints with Large Language Models

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Voboril, Florentina Ramaswamy, Vaidyanathan Peruvemba Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

Streamlining constraints (or streamliners, for short) narrow the search space, enhancing the speed and feasibility of solving complex constraint satisfaction problems. Traditionally, streamliners were crafted manually or generated through systematically combined atomic constraints with high-effort offline testing. Our approach utilizes the creativity of Large Language Models (LLMs) to propose effective streamliners for problems specified in the MiniZinc constraint programming language and integrates feedback to the LLM with quick empirical tests for validation. Evaluated across seven diverse constraint satisfaction problems, our method achieves substantial runtime reductions. We compare the results to obfuscated and disguised variants of the problem to see whether the results depend on LLM memorization. We also analyze whether longer off-line runs improve the quality of streamliners and whether the LLM can propose good combinations of streamliners. Copyright © 2024, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

A Structural complexity Analysis of Hierarchical Task Network Planning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Brand, Cornelius Ganian, Robert Inerney, Fion Mc Wietheger, Simon Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Telefónica Scientific Research Barcelona Spain

We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems. Copyright © 2024, The Authors. All rights reserved.

关键词： Complex networks

***: Compressing Linear Set Diagrams

学校读者我要写书评

暂无评论

arXiv 2023年

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

Linear diagrams are used to visualize set systems by depicting set memberships as horizontal line segments in a matrix, where each set is represented as a row and each element as a column. Each such line segment of a set is shown in a contiguous horizontal range of cells of the matrix indicating that the corresponding elements in the columns belong to the set. As each set occupies its own row in the matrix, the total height of the resulting visualization is as large as the number of sets in the instance. Such a linear diagram can be visually sparse and intersecting sets containing the same element might be represented by distant rows. To alleviate such undesirable effects, we present ***, a new approach that achieves a more space-efficient representation of linear diagrams. First, we minimize the total number of gaps in the horizontal segments by reordering columns, a criterion that has been shown to increase readability in linear diagrams. The main difference of *** to linear diagrams is that multiple non-intersecting sets can be positioned in the same row of the matrix. Furthermore, we present several different rendering variations for a matrix-based representation that utilize the proposed row compression. We implemented the different steps of our approach in a visualization pipeline using integer-linear programming, and suitable heuristics aiming at sufficiently fast computations in practice. We conducted both a quantitative evaluation and a small-scale user experiment to compare the effects of compressing linear diagrams. © 2023, CC BY.

关键词： Matrix algebra

Splitting Plane Graphs to Outerplanarity

学校读者我要写书评

暂无评论

arXiv 2023年

作者： 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. Finally, we provide upper and lower bounds for certain families of maximal planar graphs. © 2023, CC BY.

关键词： Polynomial approximation

Layered area-proportional rectangle contact representations

学校读者我要写书评

暂无评论

arXiv 2021年

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

We investigate two optimization problems on area-proportional rectangle contact representations for layered, embedded planar graphs. The vertices are represented as interior-disjoint unit-height rectangles of prescribed widths, grouped in one row per layer, and each edge is ideally realized as a rectangle contact of positive length. Such rectangle contact representations find applications in semantic word or tag cloud visualizations, where a collection of words is displayed such that pairs of semantically related words are close to each other. In this paper, we want to maximize the number of realized rectangle contacts or minimize the overall area of the rectangle contact representation, while avoiding any false adjacencies. We present a network flow model for area minimization, a linear-time algorithm for contact maximization of two-layer graphs, and an ILP model for maximizing contacts of k-layer graphs. © 2021, CC BY.

关键词： Semantics

Coloring random graphs online without creating monochromatic subgraphs 11

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic...

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Torsten Mutze Thomas Rast Reto Spohel Institute of Theoretical Computer Science Algorithms and Complexity Group

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph G_(n,p) on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of G_(n,p) are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r≥2 this problem has a threshold p0(F, r, n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of G_(n,p) that is valid w.r.t. F online, and for any function p(n)=ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic twoplayer game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a valueγ=γ(F,r) such that the threshold of the probabilistic problem is given by p0(F, r, n) = n~(-γ). Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of G_(n,p) online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n~(-γ)).

关键词： Color Fluorine (F) vertex head Valid AASS gene colored graph Line graph Probability Stochastic Processes

Minimizing crossings in constrained two-sided circular graph layouts

学校读者我要写书评

暂无评论

arXiv 2018年

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

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. Copyright © 2018, The Authors. All rights reserved.

关键词： Drawing (graphics)

On the parameterized complexity of simultaneous deletion problems 37

学校读者我要写书评

暂无评论

On the parameterized complexity of simultaneous deletion pro...

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017

作者： Agrawal, Akanksha Krithika, R. Lokshtanov, Daniel Mouawad, Amer E. Ramanujan, M.S. Department of Informatics University of Bergen Bergen Norway Institute of Mathematical Sciences HBNI Chennai India Algorithms and Complexity Group Vienna University of Technology Vienna Austria

ISBN: (纸本)9783959770552

For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, ?ai=1Ei), where the edge set of G is partitioned into a color classes, is called an a-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F1, . . ., Fa)-Deletion problem. In the latter problem, we are given an a-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph Gi - S, where Gi = (V, Ei) and 1 = i = a, is in Fi. Recently, a subset of the authors considered the aforementioned problem with F1 = . . . = Fa being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and a and can be solved in O(2O(ak)) time1. In this work, we initiate the investigation of the complexity of Simultaneous (F1, . . ., Fa)-Deletion with di erent families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the Fis is the class of bipartite graphs and the rest (if any) are forests. We show that if F1 is the family of all bipartite graphs and each of F2 = F3 = . . . = Fa is the family of all forests then the problem is fixed-parameter tractable parameterized by k and a. However, even when F1 and F2 are both the family of all bipartite graphs, then the Simultaneous (F1, F2)-Deletion problem itself is already W[1]-hard. © Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan.

关键词： Graphic methods