Results 61 to 70 of about 13,814 (224)
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results [PDF]
, 2013 We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time $n^{O(k)}$, where $k$ is the treewidth of the graph. This improves on the previous $2^{2^k}$-approximation in time $\poly(n) 2^{O(k)}$ due to Chlamt\'a\v{c} et al.
Gupta, Anupam +2 more
core +2 more sources
Knot Diagrams of Treewidth Two [PDF]
, 2020 In this paper, we study knot diagrams for which the underlying graph has treewidth two. We give a linear time algorithm for the following problem: given a knot diagram of treewidth two, does it represent the unknot? We also show that for a link diagram of treewidth two we can test in linear time if it represents the unlink.
Bodlaender, Hans L. +3 more
openaire +5 more sources
The Treewidth of Java Programs
, 2002 Intuitively, the treewidth of a graph $G$ measures how close $G$ is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on $G$, by dynamic programming along the tree structure. In the paper M.Thorup, All Structured |Programs have Small Tree-Width and Good Register Allocation [8] it is shown that the control ...
Gustedt, Jens +2 more
openaire +3 more sources
On Sparsification for Computing Treewidth [PDF]
Algorithmica, 2013 21 pages.
openaire +6 more sources
, 2018 We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $G=(V,E)$, find a shortest walk ("route") from a source $s\in V$ to a destination $t\in V$ that includes all vertices specified by a set $\mathscr{W}\subseteq V$: the
Amiri, Saeed Akhoondian +2 more
core +1 more source
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 +3 more sources
On Endomorphism Universality of Sparse Graph Classes
Journal of Graph Theory, Volume 110, Issue 2, Page 223-244, October 2025.ABSTRACT We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product,
Kolja Knauer, Gil Puig i Surroca
wiley +1 more source
An Algorithmic Metatheorem for Directed Treewidth [PDF]
, 2015 The notion of directed treewidth was introduced by Johnson, Robertson, Seymour and Thomas [Journal of Combinatorial Theory, Series B, Vol 82, 2001] as a first step towards an algorithmic metatheory for digraphs.
Oliveira, Mateus de Oliveira
core
An FPT 2-Approximation for Tree-Cut Decomposition
, 2015 The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47-66, 2015] with the help of tree-cut decompositions.
B Courcelle +17 more
core +1 more source
Tight Distance Query Reconstruction for Trees and Graphs Without Long Induced Cycles
Random Structures &Algorithms, Volume 66, Issue 4, July 2025.ABSTRACT Given access to the vertex set V$$ V $$ of a connected graph G=(V,E)$$ G=\left(V,E\right) $$ and an oracle that given two vertices u,v∈V$$ u,v\in V $$, returns the shortest path distance between u$$ u $$ and v$$ v $$, how many queries are needed to reconstruct E$$ E $$?
Paul Bastide, Carla Groenland
wiley +1 more source