A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
From MaRDI portal
Publication:5691297
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)- Kernel bounds for path and cycle problems
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Parameterized complexity of connected even/odd subgraph problems
- Positive-instance driven dynamic programming for treewidth
- Graphical Models and Message-Passing Algorithms: Some Introductory Lectures
- Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Trees, grids, and MSO decidability: from graphs to matroids
- Recursive conditioning
- Exact algorithms for intervalizing coloured graphs
- Crossing number for graphs with bounded pathwidth
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- The parametrized complexity of knot polynomials
- The minimum vulnerability problem on graphs
- An existential locality theorem
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
- Linear time approximation algorithms for~degree~constrained subgraph problems
- How to Secure Matchings Against Edge Failures
- On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
- Parameterized complexity of the spanning tree congestion problem
- Practical access to dynamic programming on tree decompositions
- A polynomial-time algorithm for finding total colorings of partial \(k\)-trees
- Optimal cuts and partitions in tree metrics in polynomial time
- Optimization problems in dotted interval graphs
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- On maximum independent set of categorical product and ultimate categorical ratios of graphs
- Clifford algebras meet tree decompositions
- Cutwidth: obstructions and algorithmic aspects
- Turbocharging treewidth heuristics
- Guard games on graphs: keep the intruder out!
- How to Secure Matchings against Edge Failures
- Improved approximation for orienting mixed graphs
- Improving robustness of next-hop routing
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
- On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
- A note on multiflows and treewidth
- I/O-efficient algorithms for graphs of bounded treewidth
- Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
- Backbone coloring of graphs with galaxy backbones
- Backbone coloring of graphs with galaxy backbones
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Approximating Pathwidth for Graphs of Small Treewidth
- An exact method for graph coloring
- Treewidth, crushing and hyperbolic volume
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- The complexity of minimum convex coloring
- Orthogonal planarity testing of bounded treewidth graphs
- Heuristic and metaheuristic methods for computing graph treewidth
- Weighted maximum-clique transversal sets of graphs
- Tree decomposition and discrete optimization problems: a survey
- The complexity of two graph orientation problems
- Treewidth governs the complexity of target set selection
- Bisimplicial separators
- Equitable colorings of bounded treewidth graphs
- The zero-visibility cops and robber game on graph products
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- On the complexity of constrained Nash equilibria in graphical games
- Tractability in constraint satisfaction problems: a survey
- Edge-disjoint odd cycles in 4-edge-connected graphs
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- The Treewidth and Pathwidth of Graph Unions
- Treewidth versus clique number. II: Tree-independence number
- Graph decompositions for cartesian products
- Treewidth computations. II. Lower bounds
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Coloring graphs without short cycles and long induced paths
- Algorithms for generalized vertex-rankings of partial k-trees
- Flexible List Colorings in Graphs with Special Degeneracy Conditions
- Incremental list coloring of graphs, parameterized by conservation
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Treewidth and logical definability of graph products
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Courcelle's theorem -- a game-theoretic approach
- The disjoint paths problem in quadratic time
- Spanners in sparse graphs
- Kernelization for feedback vertex set via elimination distance to a forest
- Tree-Width for First Order Formulae
- Parameterized Complexity of Firefighting Revisited
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- Linkless and flat embeddings in 3-space
- A Modern View on Stability of Approximation
- Constructive linear time algorithms for branchwidth
- Local Hadwiger's conjecture
- On the colored Tutte polynomial of a graph of bounded treewidth
- Completing networks using observed data
- Collective tree spanners in graphs with bounded parameters
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)
