Results 111 to 120 of about 4,776 (247)
Treewidth 2 in the Planar Graph Product Structure Theorem [PDF]
Discrete Mathematics & Theoretical Computer ScienceWe prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any
Marc Distel +4 more
doaj +1 more source
A Strategy for Dynamic Programs: Start over and Muddle through [PDF]
Logical Methods in Computer Science, 2019 In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic.
Samir Datta +4 more
doaj +1 more source
The product structure of squaregraphs
Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham +3 more
wiley +1 more source
Robust transshipment problem under consistent flow constraints
Networks, Volume 83, Issue 1, Page 53-82, January 2024.Abstract In this article, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so‐called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc,
Christina Büsing +2 more
wiley +1 more source
, 2005 Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a tree decomposition of small width. Both theoretical results, establishing the asymptotic computational complexity of the problem, as experimental work on ...
openaire +4 more sources
Treewidth distance on phylogenetic trees [PDF]
Theoretical Computer Science, 2018 In this article we study the treewidth of the \emph{display graph}, an auxiliary graph structure obtained from the fusion of phylogenetic (i.e., evolutionary) trees at their leaves. Earlier work has shown that the treewidth of the display graph is bounded if the trees are in some formal sense topologically similar.
Steven Kelk +2 more
openaire +5 more sources
Augmenting Naïve Bayes Classifiers with k-Tree Topology
MathematicsThe Bayesian network is a directed, acyclic graphical model that can offer a structured description for probabilistic dependencies among random variables.
Fereshteh R. Dastjerdi, Liming Cai
doaj +1 more source
Approximating the Treewidth of AT-Free Graphs
Discrete Applied Mathematics, 2000 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bouchitté, Vincent, Todinca, Ioan
openaire +6 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
International Journal of Foundations of Computer Science, 1993 In this paper we show that the treewidth of a circle graph can be computed in polynomial time. A circle graph is a graph that is isomorphic to the intersection graph of a finite collection of chords of a circle. The TREEWIDTH problem can be viewed upon as the problem of finding a chordal embedding of the graph that minimizes the clique number.
openaire +7 more sources