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

Longest Cycle above Erdos–Gallai Bound

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Sagunov, Danil Department of Informatics University of Bergen Norway St. Petersburg Department of V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria

In 1959, Erdos and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2O(k) · nO(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G) + k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. © 2022, CC BY.

关键词： Graph theory

Parameterized algorithms for Queue Layouts 28th

学校读者我要写书评

暂无评论

Parameterized Algorithms for Queue Layouts

28th International Symposium on Graph Drawing and Network Visualization, GD 2020

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Bruxelles Belgium Dipartimento di Ingegneria Università degli Studi di Perugia Perugia Italy

ISBN: (纸本)9783030687656

An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h. © 2020, Springer Nature Switzerland AG.

关键词： Parameter estimation

Independent sets of dynamic rectangles: algorithms and experiments

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

We study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on dynamic sets of O(n) axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update (insertion/deletion) model for two types of rectangles: (i) uniform height and width and (ii) uniform height and arbitrary width. These types of dynamic vertex update problems arise, e.g., in interactive map labeling. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of O(Δ) update time (where Δ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2(1 + 1/k) and update time O(k2log n) for k ∈ . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of uniform height and arbitrary width rectangles with O(ω log n) update time, where ω is the largest number of maximal cliques stabbed by any axis-parallel line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution size and update time for synthetic and real-world map labeling data sets. Copyright © 2020, The Authors. All rights reserved.

关键词： Geometry

Turbocharging treewidth-bounded Bayesian network structure learning

学校读者我要写书评

暂无评论

arXiv 2020年

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

We present a new approach for learning the structure of a treewidth-bounded Bayesian Network (BN). The key to our approach is applying an exact method (based on MaxSAT) locally, to improve the score of a heuristically computed BN. This approach allows us to scale the power of exact methods-so far only applicable to BNs with several dozens of random variables-to large BNs with several thousands of random variables. Our experiments show that our method improves the score of BNs provided by state-of-the-art heuristic methods, often significantly. Copyright © 2020, The Authors. All rights reserved.

关键词： Random variables

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