Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
From MaRDI portal
(Redirected from Publication:4895809)
Recommendations
Cited in
(only showing first 100 items - show all)- Derivation of algorithms for cutwidth and related graph layout parameters
- Treewidth for graphs with small chordality
- Algorithms for generalized vertex-rankings of partial k-trees
- Edge and node searching problems on trees
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Algorithms and obstructions for linear-width and related search parameters
- Counting \(H-\)colorings of partial \(k-\)trees
- Cutwidth: obstructions and algorithmic aspects
- Counting linear extensions: parameterizations by treewidth
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- The parametrized complexity of knot polynomials
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximate search strategies for weighted trees
- Crossing number for graphs with bounded pathwidth
- On the complexity of computing treebreadth
- On structural parameterizations of the edge disjoint paths problem
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- New width parameters for SAT and \#SAT
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Finding small-width connected path decompositions in polynomial time
- Non-deterministic graph searching in trees
- Linear rank-width and linear clique-width of trees
- On compiling structured CNFs to OBDDs
- Imbalance is fixed parameter tractable
- Node-searching problem on block graphs
- Exact algorithms for intervalizing coloured graphs
- Complexity and monotonicity results for domination games
- Solving projected model counting by utilizing treewidth and its limits
- Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
- Typical sequences revisited -- computing width parameters of graphs
- A c^k n 5-approximation algorithm for treewidth
- Faster computation of path-width
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- The point-set embeddability problem for plane graphs
- A basic parameterized complexity primer
- Fixed-parameter tractability of treewidth and pathwidth
- Approximating the pathwidth of outerplanar graphs
- Finite integer index of pathwidth and treewidth
- An upper bound for resolution size: characterization of tractable SAT instances
- Strengthening Erdős -- Pósa property for minor-closed graph classes
- Parameterized Complexity Results for 1-safe Petri Nets
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- On compiling structured CNFs to OBDDs
- scientific article; zbMATH DE number 4173000 (Why is no real title available?)
- Kernelization using structural parameters on sparse graph classes
- Characterizing width two for variants of treewidth
- Pathwidth of Circular-Arc Graphs
- scientific article; zbMATH DE number 176762 (Why is no real title available?)
- The complexity of minimum convex coloring
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- scientific article; zbMATH DE number 1323192 (Why is no real title available?)
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- A simpler self-reduction algorithm for matroid path-width
- Constructive linear time algorithms for branchwidth
- Treewidth and pathwidth of permutation graphs
- Confronting intractability via parameters
- Algorithms for solving problems on graphs of bounded pathwidth
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- scientific article; zbMATH DE number 219268 (Why is no real title available?)
- The Pathwidth and Treewidth of Cographs
- Computing the pathwidth of directed graphs with small vertex cover
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Finding branch-decompositions of matroids, hypergraphs, and more
- A faster tree-decomposition based algorithm for counting linear extensions
- Finding branch-decompositions of matroids, hypergraphs, and more
- Utilizing treewidth for quantitative reasoning on epistemic logic programs
- Optimizing tree decompositions in MSO
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Computing Tree Decompositions
- An improvement of Reed's treewidth approximation
- The pathwidth and treewidth of cographs
- A linear fixed parameter tractable algorithm for connected pathwidth
- A win-win algorithm for the (k+1)-LST/k-pathwidth problem
- scientific article; zbMATH DE number 7278018 (Why is no real title available?)
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- scientific article; zbMATH DE number 7310078 (Why is no real title available?)
- Computational aspects of treewidth for graph
- scientific article; zbMATH DE number 7310159 (Why is no real title available?)
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- An improved algorithm for finding tree decompositions of small width
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- From edge decomposition formulae to composition algorithms
- Pathwidth is NP-Hard for Weighted Trees
- Excluded Forest Minors and the Erdős–Pósa Property
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
- scientific article; zbMATH DE number 7651203 (Why is no real title available?)
- Graph-Theoretic Concepts in Computer Science
- A 3-approximation for the pathwidth of Halin graphs
- A 3-approximation for the pathwidth of Halin graphs
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
- Faster graph coloring in polynomial space
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Computing the vertex separation of unicyclic 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)
