Results 21 to 30 of about 13,814 (224)
Embedding phylogenetic trees in networks of low treewidth [PDF]
Embedded Systems and Applications, 2022 Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods ...
L. Iersel, Mark Jones, Mathias Weller
semanticscholar +1 more source
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
Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth [PDF]
Advances in Combinatorics, 2021 A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$-_free_ if no induced subgraph of $G$ is ...
Tara Abrishami +3 more
semanticscholar +1 more source
Treewidth of Grid Subsets [PDF]
Combinatorica, 2017 15 pages, no ...
Sergey Norin +2 more
openaire +2 more sources
Metric Dimension Parameterized By Treewidth [PDF]
Algorithmica, 2021 AbstractA resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer.
Édouard Bonnet +2 more
openaire +7 more sources
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
On the Treewidth of Dynamic Graphs [PDF]
Theoretical Computer Science, 2013 Dynamic graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modelling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability.
Bernard Mans, Luke Mathieson
openaire +4 more sources
Patterns with Bounded Treewidth [PDF]
Information and Computation, 2012 We show that any parameter of patterns that is an upper bound for the treewidth of appropriate encodings of patterns as relational structures, if restricted to a constant, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify a new such parameter, called the scope coincidence degree.
Markus L. Schmid, Daniel Reidenbach
openaire +2 more sources
Threshold Treewidth and Hypertree Width [PDF]
Journal of Artificial Intelligence Research, 2020 Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction Problem (CSP). When either of these parameters is bounded by a constant, then CSP becomes solvable in polynomial time. However, here the order of the polynomial in the running time depends on the width, and this is known
Ganian, Robert +3 more
openaire +3 more sources