Results 51 to 60 of about 11,104 (228)
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 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
Short note of supertree-width and n-Superhypertree-width [PDF]
Neutrosophic Sets and SystemsThis paper investigates the properties of tree-width and related graph width parameters for n SuperHyperGraphs, a broader generalization of hypergraphs.
Takaaki Fujita
doaj +1 more source
Tractable Inference for Hybrid Bayesian Networks with NAT-Modeled Dynamic Discretization
Proceedings of the International Florida Artificial Intelligence Research Society Conference, 2022 Hybrid BNs (HBNs) extend Bayesian networks (BNs) to both discrete and continuous variables. Among inference methods for HBNs, we focus on dynamic discretization (DD) that converts HBN to discrete BN for inference.
Yang Xiang, Hanwen Zheng
doaj +1 more source
Tree decompositions and social graphs
, 2016 Recent work has established that large informatics graphs such as social and information networks have non-trivial tree-like structure when viewed at moderate size scales.
Adcock, Aaron B. +2 more
core +1 more source
Recoloring via Modular Decomposition
Journal of Graph Theory, Volume 111, Issue 4, Page 113-123, April 2026.ABSTRACT The reconfiguration graph of the k‐colorings of a graph G, denoted R k ( G ), is the graph whose vertices are the k‐colorings of G and two colorings are adjacent in R k ( G ) if they differ in color on exactly one vertex. A graph G is said to be recolorable if R ℓ ( G ) is connected for all ℓ ≥ χ ( G ) + 1.
Manoj Belavadi +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