A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
From MaRDI portal
Recommendations
- An improved algorithm for finding tree decompositions of small width
- A simple linear-time algorithm for finding path-decompositions of small width
- Algorithms finding tree-decompositions of graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Approximate tree decompositions of planar graphs in linear time
Cited in
(only showing first 100 items - show all)- Some tractable instances of interval data minmax regret problems
- Treewidth and logical definability of graph products
- A spectral lower bound for the treewidth of a graph and its consequences
- Derivation of algorithms for cutwidth and related graph layout parameters
- The parameterized complexity of the induced matching problem
- Computational properties of argument systems satisfying graph-theoretic constraints
- On problems without polynomial kernels
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- All structured programs have small tree width and good register allocation
- Efficient Union-Find for planar graphs and other sparse graph classes
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Treewidth for graphs with small chordality
- On interval routing schemes and treewidth
- Splitting a graph into disjoint induced paths or cycles.
- Algorithms for generalized vertex-rankings of partial k-trees
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Algorithms and obstructions for linear-width and related search parameters
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Counting \(H-\)colorings of partial \(k-\)trees
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Listing all potential maximal cliques of a graph
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Safe sets in graphs: graph classes and structural parameters
- Treewidth distance on phylogenetic trees
- Structure and algorithms for (cap, even hole)-free graphs
- Recoloring graphs via tree decompositions
- A faster parameterized algorithm for pseudoforest deletion
- Matchings with lower quotas: algorithms and complexity
- Parameterized algorithms for stable matching with ties and incomplete lists
- Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
- Turbocharging treewidth heuristics
- Clifford algebras meet tree decompositions
- Cutwidth: obstructions and algorithmic aspects
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Explicit linear kernels for packing problems
- Counting linear extensions: parameterizations by treewidth
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- Parameterized complexity of the spanning tree congestion problem
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Two feedback problems for graphs with bounded tree-width
- Tree decompositions with small cost
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Computing the branchwidth of interval graphs
- Querying linguistic treebanks with monadic second-order logic in linear time
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- Parameterized complexity of vertex colouring
- Chordal bipartite graphs of bounded tree- and clique-width
- Maximum likelihood bounded tree-width Markov networks
- Reduction algorithms for graphs of small treewidth
- The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
- The longest common subsequence problem for sequences with nested arc annotations.
- The parametrized complexity of knot polynomials
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- An existential locality theorem
- Computing crossing numbers in quadratic time
- Improved Steiner tree algorithms for bounded treewidth
- Spanners of bounded degree graphs
- The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
- A new ant colony optimization algorithm for the lower bound of sum coloring problem
- Constrained-path labellings on graphs of bounded clique-width
- Crossing number for graphs with bounded pathwidth
- On the complexity of computing treebreadth
- Practical access to dynamic programming on tree decompositions
- On structural parameterizations of the edge disjoint paths problem
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- Confluence up to garbage in graph transformation
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- Upper and lower degree-constrained graph orientation with minimum penalty
- Orthogonal planarity testing of bounded treewidth graphs
- Fast and parallel decomposition of constraint satisfaction problems
- Measuring power in coalitional games with friends, enemies and allies
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Parameterized complexity of \((A,\ell)\)-path packing
- Treewidth of the generalized Kneser graphs
- An analysis of the parameterized complexity of periodic timetabling
- An improved planar graph product structure theorem
- Minimum \(t\)-spanners on subcubic graphs
- Structural parameterizations with modulator oblivion
- Space-efficient vertex separators for treewidth
- The tree-width of C
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Bundled crossings revisited
- Sketched representations and orthogonal planarity of bounded treewidth graphs
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- How to compute digraph width measures on directed co-graphs
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Branch-depth: generalizing tree-depth of graphs
- Weighted total acquisition
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- An improvement of Reed's treewidth approximation
- Discrete optimization methods for group model selection in compressed sensing
- Frameworks for designing in-place graph algorithms
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- New width parameters for SAT and \#SAT
- On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
This page was built for publication: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5691297)
