Cutwidth I: A linear time fixed parameter algorithm

DOI10.1016/j.jalgor.2004.12.001zbMath1161.68856OpenAlexW2083103669WikidataQ59567822 ScholiaQ59567822MaRDI QIDQ5462383

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

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.001

zbMATH Keywords

PathwidthGraph layoutTreewidthCutwidth

Mathematics Subject Classification ID

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

Related Items (33)

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 ⋮ Branch and bound for the cutwidth minimization problem ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ A branch-and-bound algorithm for the minimum cut linear arrangement problem ⋮ Reachability in Graph Transformation Systems and Slice Languages ⋮ Scheduling series-parallel task graphs to minimize peak memory ⋮ 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 ⋮ 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 ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time ⋮ 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 ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Invariants of graph drawings in the plane ⋮ On spanning tree congestion of graphs ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Myhill-Nerode Methods for Hypergraphs ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

This page was built for publication: Cutwidth I: A linear time fixed parameter algorithm