Cutwidth II: Algorithms for partial w-trees of bounded degree

DOI10.1016/j.jalgor.2004.12.003zbMath1161.68857DBLPjournals/jal/ThilikosSB05aOpenAlexW2065528988WikidataQ59567829 ScholiaQ59567829MaRDI QIDQ5462384

Dimitrios M. Thilikos, Hans L. Bodlaender, Maria J. Serna

Publication date: 1 August 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.12.003

zbMATH Keywords

PathwidthGraph layoutTreewidthCutwidth

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (29)

Decomposability of a class of \(k\)-cutwidth critical graphs ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Computing Tree Decompositions ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ A branch-and-bound algorithm for the minimum cut linear arrangement problem ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Unnamed Item ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Unnamed Item ⋮ Typical sequences revisited -- computing width parameters of graphs ⋮ Imbalance is fixed parameter tractable ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Confronting intractability via parameters ⋮ Unnamed Item ⋮ Cutwidth: obstructions and algorithmic aspects ⋮ The structure of graphs not admitting a fixed immersion ⋮ On cutwidth parameterized by vertex cover ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time ⋮ Multistart search for the cyclic cutwidth minimization problem ⋮ The treewidth of line graphs ⋮ Fixed-parameter algorithms for protein similarity search under mRNA structure constraints ⋮ Derivation of algorithms for cutwidth and related graph layout parameters ⋮ A Variable Neighbourhood Search approach to the Cutwidth Minimization Problem ⋮ Decompositions of critical trees with cutwidth \(k\) ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

This page was built for publication: Cutwidth II: Algorithms for partial w-trees of bounded degree