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 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
- Crossing number for graphs with bounded pathwidth
- The point-set embeddability problem for plane graphs
- Faster computation of path-width
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Approximating Pathwidth for Graphs of Small Treewidth
- On compiling structured CNFs to OBDDs
- Treelength of series-parallel graphs
- A 3-approximation for the pathwidth of Halin graphs
- An improvement of Reed's treewidth approximation
- Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
- A simpler self-reduction algorithm for matroid path-width
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Computing Tree Decompositions
- Solving projected model counting by utilizing treewidth and its limits
- A strengthening and an efficient implementation of Alon-Tarsi list coloring method
- Finding branch-decompositions of matroids, hypergraphs, and more
- From edge decomposition formulae to composition algorithms
- Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
- New width parameters for SAT and \#SAT
- Dynamic algorithms for graphs with treewidth 2
- Typical sequences revisited -- computing width parameters of graphs
- An upper bound for resolution size: characterization of tractable SAT instances
- On the complexity of the storyplan problem
- On the complexity of the storyplan problem
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- A win-win algorithm for the \((k+1)\)-LST/\(k\)-pathwidth problem
- Computational aspects of treewidth for graph
- 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
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)
