Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
From MaRDI portal
Publication:4895809
Recommendations
Cited in
(only showing first 100 items - show all)- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Confronting intractability via parameters
- The complexity of minimum convex coloring
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Approximate search strategies for weighted trees
- The pathwidth and treewidth of cographs
- scientific article; zbMATH DE number 7310159 (Why is no real title available?)
- On the parameterized complexity of layered graph drawing
- Characterizing width two for variants of treewidth
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Pathwidth is NP-Hard for Weighted Trees
- Algorithms and obstructions for linear-width and related search parameters
- Strengthening Erdős -- Pósa property for minor-closed graph classes
- I/O-efficient algorithms for graphs of bounded treewidth
- A \(c^k n\) 5-approximation algorithm for treewidth
- Imbalance is fixed parameter tractable
- Kernelization using structural parameters on sparse graph classes
- Constraint satisfaction with bounded treewidth revisited
- Excluded Forest Minors and the Erdős–Pósa Property
- A faster tree-decomposition based algorithm for counting linear extensions
- Graph-Theoretic Concepts in Computer Science
- A faster tree-decomposition based algorithm for counting linear extensions
- Algorithms for solving problems on graphs of bounded pathwidth
- Treewidth for graphs with small chordality
- A simple linear-time algorithm for finding path-decompositions of small width
- Pathwidth of Circular-Arc Graphs
- Algorithms for generalized vertex-rankings of partial k-trees
- Counting linear extensions: parameterizations by treewidth
- A graph search algorithm for indoor pursuit/evasion
- The Pathwidth and Treewidth of Cographs
- The complexity of subgraph isomorphism for classes of partial k-trees
- Symbolic techniques in satisfiability solving
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- The parametrized complexity of knot polynomials
- Online promise problems with online width metrics
- List matrix partitions of chordal graphs
- Linear rank-width and linear clique-width of trees
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Exact algorithms for intervalizing coloured graphs
- A linear fixed parameter tractable algorithm for connected pathwidth
- Constructive linear time algorithms for branchwidth
- Counting \(H-\)colorings of partial \(k-\)trees
- A linear edge kernel for two-layer crossing minimization
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- Computing the vertex separation of unicyclic graphs
- Edge and node searching problems on trees
- Derivation of algorithms for cutwidth and related graph layout parameters
- Equitable colorings of bounded treewidth graphs
- Finding small-width connected path decompositions in polynomial time
- A 3-approximation for the pathwidth of Halin graphs
- Fixed-parameter tractability of treewidth and pathwidth
- A basic parameterized complexity primer
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- scientific article; zbMATH DE number 176762 (Why is no real title available?)
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- scientific article; zbMATH DE number 4173000 (Why is no real title available?)
- On compiling structured CNFs to OBDDs
- Complexity and monotonicity results for domination games
- Node-searching problem on block graphs
- Approximating the pathwidth of outerplanar graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Computing the pathwidth of directed graphs with small vertex cover
- scientific article; zbMATH DE number 219268 (Why is no real title available?)
- An improved algorithm for finding tree decompositions of small width
- Non-deterministic graph searching in trees
- Treewidth and pathwidth of permutation graphs
- On the routing problems in graphs with ordered forbidden transitions
- scientific article; zbMATH DE number 7471715 (Why is no real title available?)
- Sum-of-local-effects data structures for separable graphs
- On the parameterized complexity of s-club cluster deletion problems
- Fast FPT-approximation of branchwidth
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Parameterized Complexity Results for 1-safe Petri Nets
- On the parameterized complexity of \(s\)-club cluster deletion problems
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- On integer linear programs for treewidth based on perfect elimination orderings
- Recognizing map graphs of bounded treewidth
- Solving infinite-domain CSPs using the patchwork property
- scientific article; zbMATH DE number 7278018 (Why is no real title available?)
- scientific article; zbMATH DE number 7651203 (Why is no real title available?)
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
- Finite integer index of pathwidth and treewidth
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Edge-treewidth: algorithmic and combinatorial properties
- scientific article; zbMATH DE number 7310078 (Why is no real title available?)
- An improved parameterized algorithm for treewidth
- On the complexity of computing treebreadth
- A Modern View on Stability of Approximation
- Finding branch-decompositions of matroids, hypergraphs, and more
- Utilizing treewidth for quantitative reasoning on epistemic logic programs
- Cutwidth: obstructions and algorithmic aspects
- On structural parameterizations of the edge disjoint paths problem
- Faster graph coloring in polynomial space
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
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)
