Tree-width, path-width, and cutwidth
From MaRDI portal
The authors prove an asymptotic estimate of the cutwidth \(\text{c} (G)\) of a graph \(G\) on \(n\) vertices in terms of its tree-width \(\text{tw} (G)\).
Cites work
- 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
- 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?)
- 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
(40)- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- On 3-cutwidth critical graphs
- Cutwidth: obstructions and algorithmic aspects
- Submodular unsplittable flow on trees
- On Tseitin formulas, read-once branching programs and treewidth
- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- One-visibility cops and robber on trees: optimal cop-win strategies
- Decomposability of a class of \(k\)-cutwidth critical graphs
- Decompositions of critical trees with cutwidth k
- Computing the chromatic number using graph decompositions via matrix rank
- Improved algorithms for some competitive location centroid problems on paths, trees and graphs
- Characterizations of \(k\)-cutwidth critical trees
- The Firefighter Problem: A Structural Analysis
- An upper bound for resolution size: characterization of tractable SAT instances
- Submodular unsplittable flow on trees
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
- Large angle crossing drawings of planar graphs in subquadratic area
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Randomly coloring graphs of logarithmically bounded pathwidth
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Neighbourhood-width of trees
- The treewidth of 2-section of hypergraphs
- Metric Embedding via Shortest Path Decompositions
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- The firefighter problem: further steps in understanding its complexity
- Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
- Strong SDP based bounds on the cutwidth of a graph
- Edge-treewidth: algorithmic and combinatorial properties
- Population-based iterated greedy algorithm for the S-labeling problem
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Aspmc: new frontiers of algebraic answer set counting
- Slim tree-cut width
- The complexity of subgraph isomorphism for classes of partial k-trees
- An approximation algorithm for zero forcing
- Edge-maximal graphs with cutwidth at most three
- Some bounds on the threshold dimension of graphs
- Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
- The treewidth of line graphs
- Visualizing treewidth
- Visualizing treewidth
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)
