Tree-width, path-width, and cutwidth
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3956440 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4121424 (Why is no real title available?)
- A polynomial algorithm for the min-cut linear arrangement of trees
- Complexity of Finding Embeddings in a k-Tree
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graphs with small bandwidth and cutwidth
- On minimizing width in linear layouts
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
Cited in
(34)- Cutwidth: obstructions and algorithmic aspects
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Characterizations of \(k\)-cutwidth critical trees
- Large angle crossing drawings of planar graphs in subquadratic area
- Aspmc: new frontiers of algebraic answer set counting
- Metric Embedding via Shortest Path Decompositions
- On Tseitin formulas, read-once branching programs and treewidth
- Decomposability of a class of \(k\)-cutwidth critical graphs
- Slim tree-cut width
- Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
- Decompositions of critical trees with cutwidth \(k\)
- The treewidth of line graphs
- Population-based iterated greedy algorithm for the S-labeling problem
- Computing the chromatic number using graph decompositions via matrix rank
- An upper bound for resolution size: characterization of tractable SAT instances
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
- Strong SDP based bounds on the cutwidth of a graph
- Edge-treewidth: algorithmic and combinatorial properties
- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- The complexity of subgraph isomorphism for classes of partial k-trees
- The Firefighter Problem: A Structural Analysis
- The treewidth of 2-section of hypergraphs
- Submodular unsplittable flow on trees
- Submodular unsplittable flow on trees
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- Improved algorithms for some competitive location centroid problems on paths, trees and graphs
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Neighbourhood-width of trees
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- On 3-cutwidth critical graphs
- One-visibility cops and robber on trees: optimal cop-win strategies
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Randomly coloring graphs of logarithmically bounded pathwidth
- The firefighter problem: further steps in understanding its complexity
This page was built for publication: Tree-width, path-width, and cutwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801672)
