Results 61 to 70 of about 5,860 (222)
Nordhaus-Gaddum for Treewidth [PDF]
European Journal of Combinatorics, 33.4:488-490, 2012, 2011 We prove that for every graph $G$ with $n$ vertices, the treewidth of $G$ plus the treewidth of the complement of $G$ is at least $n-2$. This bound is tight.
arxiv +1 more source
Parameterized Complexity of Equitable Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\left\lfloor n/k \right\rfloor$ or $\left\lceil n/k \right\rceil$ times.
Guilherme de C. M. Gomes +2 more
doaj +1 more source
New Algorithms for Mixed Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions.
Louis Dublois +2 more
doaj +1 more source
Practical Access to Dynamic Programming on Tree Decompositions
Algorithms, 2019 Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood.
Max Bannach, Sebastian Berndt
doaj +1 more source
Treewidth via Spined Categories (extended abstract) [PDF]
arXiv, 2021 Treewidth is a well-known graph invariant with multiple interesting applications in combinatorics. On the practical side, many NP-complete problems are polynomial-time (sometimes even linear-time) solvable on graphs of bounded treewidth. On the theoretical side, treewidth played an essential role in the proof of the celebrated Robertson-Seymour graph ...
arxiv
Cycle decompositions of pathwidth‐6 graphs
Journal of Graph Theory, Volume 94, Issue 2, Page 224-251, June 2020., 2020 Abstract Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most ⌊ ( n − 1 ) / 2 ⌋ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions.
Elke Fuchs +2 more
wiley +1 more source
Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
Algorithms, 2019 Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science.
Robert Ganian, Sebastian Ordyniak
doaj +1 more source
Fast Diameter Computation within Split Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two.
Guillaume Ducoffe +2 more
doaj +1 more source
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2020 Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour.
Vincent Cohen-Addad +3 more
semanticscholar +1 more source
Four short stories on surprising algorithmic uses of treewidth [PDF]
, 2020 This article briefly describes four algorithmic problems where the notion of treewidth is very useful. Even though the problems themselves have nothing to do with treewidth, it turns out that combining known results on treewidth allows us to easily describe very clean and high-level algorithms.
arxiv +1 more source