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

On the readability of abstract set visualizations

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Wallinger, Markus Jacobsen, Ben Kobourov, Stephen Nöllenburg, Martin The Algorithms and Complexity Group TU Wien Vienna Austria The Dept. of Computer Science University of Arizona TucsonAZ United States

Set systems are used to model data that naturally arises in many contexts: social networks have communities, musicians have genres, and patients have symptoms. Visualizations that accurately reflect the information in the underlying set system make it possible to identify the set elements, the sets themselves, and the relationships between the sets. In static contexts, such as print media or infographics, it is necessary to capture this information without the help of interactions. With this in mind, we consider three different systems for medium-sized set data, LineSets, EulerView, and MetroSets, and report the results of a controlled human-subjects experiment comparing their effectiveness. Specifically, we evaluate the performance, in terms of time and error, on tasks that cover the spectrum of static set-based tasks. We also collect and analyze qualitative data about the three different visualization systems. Our results include statistically significant differences, suggesting that MetroSets performs and scales better. © 2021, CC BY.

关键词： Visualization

Finding linear arrangements of hypergraphs with bounded cutwidth in linear time 14

学校读者我要写书评

暂无评论

Finding linear arrangements of hypergraphs with bounded cutw...

14th International Symposium on Parameterized and Exact Computation, IPEC 2019

作者： Hamm, Thekla Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959771290

Cutwidth is a fundamental graph layout parameter. It generalises to hypergraphs in a natural way and has been studied in a wide range of contexts. For graphs it is known that for a fixed constant k there is a linear time algorithm that for any given G, decides whether G has cutwidth at most k and, in the case of a positive answer, outputs a corresponding linear arrangement. We show that such an algorithm also exists for hypergraphs. © Thekla Hamm;licensed under Creative Commons License CC-BY.

关键词： Clustering algorithms

The complexity of Temporal Vertex Cover in Small-Degree Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Hamm, Thekla Klobas, Nina Mertzios, George B. Spirakis, Paul G. Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science Durham University United Kingdom Department of Computer Science University of Liverpool United Kingdom Computer Engineering & Informatics Department University of Patras Greece

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆-TVC for time-windows of a fixed-length ∆) have been established as natural extensions of the classic problem Vertex Cover on static graphs with connections to areas such as surveillance in sensor networks. In this paper, we initiate a systematic study of the complexity of TVC and ∆-TVC on sparse graphs. Our main result shows that for every ∆ ≥ 2, ∆-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between ∆-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present some fixed-parameter and approximation algorithms. Copyright © 2022, The Authors. All rights reserved.

关键词： Approximation algorithms

Graphs with Two Moplexes ⁎

学校读者我要写书评

暂无评论

Procedia Computer Science 2021年 195卷 248-256页

作者： Clément Dallard Robert Ganian Meike Hatzel Matjaž Krnc Martin Milanič FAMNIT University of Primorska Koper Slovenia IAM University of Primorska Koper Slovenia Algorithms and Complexity Group TU Wien Vienna Austria LaS Technische Universiät Berlin Berlin Germany

Moplexes are natural graph structures that arise when lifting Dirac’s classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, among others, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case, k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that the class of connected 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal s

关键词： moplex simplicial vertex avoidable vertex asteroidal number cocomparability graph Hamiltonian path

Interplay of periodic dynamics and noise: Insights from a simple adaptive system

学校读者我要写书评

暂无评论

Physical Review E 2021年第5期104卷 054215-054215页

作者： Frederic Folz Kurt Mehlhorn Giovanna Morigi Theoretische Physik Universität des Saarlandes 66123 Saarbrücken Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus 66123 Saarbrücken Germany

We study the dynamics of a simple adaptive system in the presence of noise and periodic damping. The system is composed by two paths connecting a source and a sink, and the dynamics is governed by equations that usually describe food search of the paradigmatic Physarum polycephalum. In this work we assume that the two paths undergo damping whose relative strength is periodically modulated in time, and we analyze the dynamics in the presence of stochastic forces simulating Gaussian noise. We identify different responses depending on the modulation frequency and on the noise amplitude. At frequencies smaller than the mean dissipation rate, the system tends to switch to the path which minimizes dissipation. Synchronous switching occurs at an optimal noise amplitude which depends on the modulation frequency. This behavior disappears at larger frequencies, where the dynamics can be described by the time-averaged equations. Here we find metastable patterns that exhibit the features of noise-induced resonances.

关键词： Dynamics of networks Stochastic dynamical systems Stochastic networks

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Focke, Jacob Marx, Dániel Mc Inerney, Fionn Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩S| ∈ σ for every u ∈ S, and |N(v) ∩S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite;rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ, ρ) is m-structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop + 2 if (σ, ρ) is not m-structured for any m ≥ 2, • cσ,ρ = max{stop, rtop}+ 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise, we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to σ = algorithms and ρ = algorithms, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw · nO(1). Despite the unusually delicate definition of cσ,ρ, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ−Ε)tw ·nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the C

关键词： Trees (mathematics)

Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bekos, Michael A. Gronemann, Martin Montecchiani, Fabrizio Symvonis, Antonios Department of Mathematics University of Ioannina Ioannina Greece Algorithms and Complexity Group TU Wien Vienna Austria Department of Engineering University of Perugia Perugia Italy School of Applied Mathematical & Physical Sciences National Technical University of Athens Athens Greece

We continue the study of the area requirement of convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces and computes a convex straight-line drawing with edge-vertex resolution at least 12 on an integer grid of size (n − 2 + a) × (n − 2 + a), where a = min{n − 3, f}. Our result improves the previously best-known area bound of (3n − 7) × (3n − 7)/2 by Chrobak, Goodrich and Tamassia. © 2022, CC0.

关键词：

Unit disk representations of embedded trees, outerplanar and multi-legged graphs

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Löffler, Maarten Nickel, Soeren Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Department of Computing and Information Sciences Utrecht University Algorithms and Complexity Group TU Wien Vienna Austria

A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices. © 2021, CC BY.

关键词： Trees (mathematics)

Extending nearly complete 1-planar drawings in polynomial time 45

学校读者我要写书评

暂无评论

Extending nearly complete 1-planar drawings in polynomial ti...

45th International Symposium on Mathematical Foundations of Computer Science, MFCS 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 Department of Information and Computing Sciences Utrecht University Netherlands

ISBN: (纸本)9783959771597

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 algorithm. © Nathalie Bertrand;licensed under Creative Commons License CC-BY 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).

关键词： Polynomial approximation