Results 61 to 70 of about 4,791 (239)
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
Discrete Applied Mathematics, 2004 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bouchitté, Vincent +3 more
openaire +3 more sources
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
Algorithms, 2018 Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen +3 more
doaj +1 more source
European Journal of Combinatorics, 2012 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.
Joret, Gwenaël, Wood, D.
openaire +2 more sources
Balancing Bounded Treewidth Circuits [PDF]
Theory of Computing Systems, 2010 Algorithmic tools for graphs of small treewidth are used to address questions in complexity theory. For both arithmetic and Boolean circuits, it is shown that any circuit of size $n^{O(1)}$ and treewidth $O(\log^i n)$ can be simulated by a circuit of width $O(\log^{i+1} n)$ and size $n^c$, where $c = O(1)$, if $i=0$, and $c=O(\log \log n)$ otherwise ...
Jansen, Maurice, Sarma, Jayalal
openaire +3 more sources
Quantum speedups for treewidth
, 2022 In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses $O(2.616^n)$ time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space ...
Kļevickis, Vladislavs +2 more
openaire +4 more sources
Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting
International Conference on Principles of Knowledge Representation and Reasoning, 2021 Probabilistic reasoning, parameter learning, and most probable explanation inference for answer set programming have recently received growing attention.
Thomas Eiter +2 more
semanticscholar +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
Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure [PDF]
SIAM Journal on Discrete Mathematics, 2020 Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques.
Clément Dallard +2 more
semanticscholar +1 more source
Treewidth Lower Bounds with Brambles [PDF]
Algorithmica, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bodlaender, H.L. +2 more
openaire +5 more sources