Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
From MaRDI portal
Publication:4895809
DOI10.1006/JAGM.1996.0049zbMATH Open0861.68036OpenAlexW2125058377WikidataQ29396868 ScholiaQ29396868MaRDI QIDQ4895809FDOQ4895809
Authors: Ton Kloks, Hans L. Bodlaender 
Publication date: 11 May 1997
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/21989
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Cited In (only showing first 100 items - show all)
- Pathwidth of Circular-Arc Graphs
- The parametrized complexity of knot polynomials
- Exact algorithms for intervalizing coloured graphs
- Non-deterministic graph searching in trees
- On the complexity of rainbow coloring problems
- Title not available (Why is that?)
- Complexity and monotonicity results for domination games
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- I/O-efficient algorithms for graphs of bounded treewidth
- Symbolic techniques in satisfiability solving
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- The complexity of minimum convex coloring
- Equitable colorings of bounded treewidth graphs
- Algorithms for generalized vertex-rankings of partial k-trees
- Constructive linear time algorithms for branchwidth
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- A 3-approximation for the pathwidth of Halin graphs
- The Pathwidth and Treewidth of Cographs
- On Compiling Structured CNFs to OBDDs
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Excluded Forest Minors and the Erdős–Pósa Property
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Parameterized complexity of discrete Morse theory
- A \(c^k n\) 5-approximation algorithm for treewidth
- Constraint satisfaction with bounded treewidth revisited
- Treewidth for graphs with small chordality
- Online promise problems with online width metrics
- A linear edge kernel for two-layer crossing minimization
- Approximating the pathwidth of outerplanar graphs
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- Kernelization using structural parameters on sparse graph classes
- On the complexity of computing treebreadth
- Title not available (Why is that?)
- Approximate search strategies for weighted trees
- On the parameterized complexity of layered graph drawing
- A graph search algorithm for indoor pursuit/evasion
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Linear rank-width and linear clique-width of trees
- Edge and node searching problems on trees
- Finding small-width connected path decompositions in polynomial time
- A Basic Parameterized Complexity Primer
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- Strengthening Erdős -- Pósa property for minor-closed graph classes
- The complexity of subgraph isomorphism for classes of partial k-trees
- Title not available (Why is that?)
- Confronting intractability via parameters
- The pathwidth and treewidth of cographs
- A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
- Algorithms and obstructions for linear-width and related search parameters
- Counting \(H-\)colorings of partial \(k-\)trees
- Computing the pathwidth of directed graphs with small vertex cover
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Computing the vertex separation of unicyclic graphs
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Node-searching problem on block graphs
- Characterizing width two for variants of treewidth
- Derivation of algorithms for cutwidth and related graph layout parameters
- Title not available (Why is that?)
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Graph-Theoretic Concepts in Computer Science
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- A faster tree-decomposition based algorithm for counting linear extensions
- Imbalance is fixed parameter tractable
- Title not available (Why is that?)
- A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Counting linear extensions: parameterizations by treewidth
- Pathwidth is NP-Hard for Weighted Trees
- A simple linear-time algorithm for finding path-decompositions of small width
- List matrix partitions of chordal graphs
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Crossing number for graphs with bounded pathwidth
- Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs
- Cutwidth: obstructions and algorithmic aspects
- Approximating Pathwidth for Graphs of Small Treewidth
- Faster Computation of Path-Width
- A Modern View on Stability of Approximation
- Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
- From edge decomposition formulae to composition algorithms
- Fast FPT-approximation of branchwidth
- Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming
- On the routing problems in graphs with ordered forbidden transitions
- Sum-of-local-effects data structures for separable graphs
- Dynamic algorithms for graphs with treewidth 2
- New width parameters for SAT and \#SAT
- On the parameterized complexity of s-club cluster deletion problems
- On the parameterized complexity of \(s\)-club cluster deletion problems
- Solving projected model counting by utilizing treewidth and its limits
- Solving infinite-domain CSPs using the patchwork property
- On structural parameterizations of the edge disjoint paths problem
- Finite Integer Index of Pathwidth and Treewidth
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Computing Tree Decompositions
- Myhill-Nerode Methods for Hypergraphs
- On integer linear programs for treewidth based on perfect elimination orderings
- Recognizing map graphs of bounded treewidth
- Edge-treewidth: algorithmic and combinatorial properties
This page was built for publication: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4895809)
