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)- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Treewidth and pathwidth of permutation graphs
- The point-set embeddability problem for plane graphs
- scientific article; zbMATH DE number 7278018 (Why is no real title available?)
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Graph-Theoretic Concepts in Computer Science
- A faster tree-decomposition based algorithm for counting linear extensions
- A faster tree-decomposition based algorithm for counting linear extensions
- An improved parameterized algorithm for treewidth
- Faster graph coloring in polynomial space
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Imbalance is fixed parameter tractable
- An improved algorithm for finding tree decompositions of small width
- Faster computation of path-width
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- scientific article; zbMATH DE number 219268 (Why is no real title available?)
- scientific article; zbMATH DE number 7471715 (Why is no real title available?)
- Typical sequences revisited -- computing width parameters of graphs
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Treelength of series-parallel graphs
- Algorithms for solving problems on graphs of bounded pathwidth
- Counting linear extensions: parameterizations by treewidth
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- Fixed-parameter tractability of treewidth and pathwidth
- 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
- Pathwidth is NP-Hard for Weighted Trees
- Exact algorithms for intervalizing coloured graphs
- Crossing number for graphs with bounded pathwidth
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- The parametrized complexity of knot polynomials
- Computational aspects of treewidth for graph
- Pathwidth of Circular-Arc Graphs
- Non-deterministic graph searching in trees
- Cutwidth: obstructions and algorithmic aspects
- Complexity and monotonicity results for domination games
- scientific article; zbMATH DE number 7310159 (Why is no real title available?)
- I/O-efficient algorithms for graphs of bounded treewidth
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- On compiling structured CNFs to OBDDs
- Approximating Pathwidth for Graphs of Small Treewidth
- Symbolic techniques in satisfiability solving
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- 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
- Finite integer index of pathwidth and treewidth
- Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
- A Modern View on Stability of Approximation
- Constructive linear time algorithms for branchwidth
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- A basic parameterized complexity primer
- A 3-approximation for the pathwidth of Halin graphs
- The Pathwidth and Treewidth of Cographs
- From edge decomposition formulae to composition algorithms
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Fast FPT-approximation of branchwidth
- Excluded Forest Minors and the Erdős–Pósa Property
- Constraint satisfaction with bounded treewidth revisited
- A \(c^k n\) 5-approximation algorithm for treewidth
- New width parameters for SAT and \#SAT
- On the routing problems in graphs with ordered forbidden transitions
- Sum-of-local-effects data structures for separable graphs
- A simpler self-reduction algorithm for matroid path-width
- Treewidth for graphs with small chordality
- Online promise problems with online width metrics
- A linear edge kernel for two-layer crossing minimization
- Dynamic algorithms for graphs with treewidth 2
- Approximating the pathwidth of outerplanar graphs
- On the parameterized complexity of s-club cluster deletion problems
- Solving projected model counting by utilizing treewidth and its limits
- On the parameterized complexity of \(s\)-club cluster deletion problems
- Kernelization using structural parameters on sparse graph classes
- A linear fixed parameter tractable algorithm for connected pathwidth
- On the complexity of computing treebreadth
- On the parameterized complexity of layered graph drawing
- An upper bound for resolution size: characterization of tractable SAT instances
- Approximate search strategies for weighted trees
- scientific article; zbMATH DE number 176762 (Why is no real title available?)
- A graph search algorithm for indoor pursuit/evasion
- Solving infinite-domain CSPs using the patchwork property
- On structural parameterizations of the edge disjoint paths problem
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Edge and node searching problems on trees
- Linear rank-width and linear clique-width of trees
- Finding small-width connected path decompositions in polynomial time
- Computing Tree Decompositions
- Utilizing treewidth for quantitative reasoning on epistemic logic programs
- On integer linear programs for treewidth based on perfect elimination orderings
- Recognizing map graphs of bounded treewidth
- Edge-treewidth: algorithmic and combinatorial properties
- A 3-approximation for the pathwidth of Halin graphs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- The complexity of subgraph isomorphism for classes of partial k-trees
- Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
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)
