Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Pathwidth is NP-Hard for Weighted Trees
- Approximating branchwidth on parametric extensions of planarity
- 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
- Comparing width parameters on graph classes
- 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
- Approximating branchwidth on parametric extensions of planarity
- On the parameterized complexity of computing st-orientations with few transitive edges
- 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
- A general framework for participatory budgeting with additional constraints
- 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
- Optimal blocks for maximizing the transaction fee revenue of bitcoin miners
- Complexity framework for forbidden subgraphs. I: The framework
- 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
- An approximation algorithm for zero forcing
- 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
- Algorithms and complexity of difference logic
- 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
- Strengthening Erdős -- Pósa property for minor-closed graph classes
- A win-win algorithm for the (k+1)-LST/k-pathwidth problem
- Confronting intractability via parameters
- On compiling structured CNFs to OBDDs
- scientific article; zbMATH DE number 7651203 (Why is no real title available?)
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Algorithms and obstructions for linear-width and related search parameters
- Finding branch-decompositions of matroids, hypergraphs, and more
- Parameterized Complexity Results for 1-safe Petri Nets
- A strengthening and an efficient implementation of Alon-Tarsi list coloring method
- On the complexity of the storyplan problem
- Counting \(H-\)colorings of partial \(k-\)trees
- On the complexity of the storyplan problem
- Computing the pathwidth of directed graphs with small vertex cover
- The pathwidth and treewidth of cographs
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
- Finding branch-decompositions of matroids, hypergraphs, and more
- Computing the vertex separation of unicyclic graphs
- Tree decompositions meet induced matchings: beyond max weight independent set
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
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)
