Results 131 to 140 of about 13,679 (262)
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
Induced subgraphs and tree decompositions V. one neighbor in a hole
Journal of Graph Theory, Volume 105, Issue 4, Page 542-561, April 2024.Abstract What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”).
Tara Abrishami +5 more
wiley +1 more source
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
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
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
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
The complexity of detecting taut angle structures on triangulations
, 2012 There are many fundamental algorithmic problems on triangulated 3-manifolds whose complexities are unknown. Here we study the problem of finding a taut angle structure on a 3-manifold triangulation, whose existence has implications for both the geometry ...
Burton, Benjamin A., Spreer, Jonathan
core +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
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2022 Marthe Bonamy +7 more
semanticscholar +1 more source
Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]
Logical Methods in Computer ScienceWe show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj +1 more source