Results 41 to 50 of about 4,791 (239)
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth [PDF]
Symposium on the Theory of Computing, 2022 We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f, and a multicut of capacity c such that f
T. Friedrich +4 more
semanticscholar +1 more source
The treewidth and pathwidth of graph unions [PDF]
SIAM Journal on Discrete Mathematics, 2022 Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show that
Bogdan Alecu +5 more
semanticscholar +1 more source
The Treewidth of Induced Graphs of Conditional Preference Networks Is Small
Information, 2016 Conditional preference networks (CP-nets) are recently an emerging topic as a graphical model for compactly representing ordinal conditional preference relations on multi-attribute domains.
Jie Liu, Jinglei Liu
doaj +1 more source
Tuza's Conjecture for Threshold Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including
Marthe Bonamy +6 more
doaj +1 more source
Clique‐width: Harnessing the power of atoms
Journal of Graph Theory, Volume 104, Issue 4, Page 769-810, December 2023., 2023 Abstract Many NP‐complete graph problems are polynomial‐time solvable on graph classes of bounded clique‐width. Several of these problems are polynomial‐time solvable on a hereditary graph class G ${\mathscr{G}}$ if they are so on the atoms (graphs with no clique cut‐set) of G ${\mathscr{G}}$.
Konrad K. Dabrowski +4 more
wiley +1 more source
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Algorithms, 2021 Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been ...
Johannes K. Fichte +3 more
doaj +1 more source
Vertex covering with capacitated trees
Networks, Volume 81, Issue 2, Page 253-277, March 2023., 2023 Abstract The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs.
Ralf Borndörfer +2 more
wiley +1 more source
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2021 The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs.
Jacob Focke +2 more
semanticscholar +1 more source
Patterns with Bounded Treewidth [PDF]
Information and Computation, 2012 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Reidenbach, Daniel, Schmid, Markus L.
openaire +2 more sources
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path [PDF]
Symposium on the Theory of Computing, 2020 Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms. Many NP-hard problems are known to be solvable in O(n · 2O(τ)) time, where τ is the treewidth of the input graph.
Sally Dong, Y. Lee, Guanghao Ye
semanticscholar +1 more source