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

DOI10.1016/J.JALGOR.2004.12.003MaRDI QIDQ5462384zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dimitrios M. Thilikos, Maria 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.003

zbMATH Keywords

CutwidthGraph layoutPathwidthTreewidth

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1875430
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Cutwidth I: A linear time fixed parameter algorithm
• scientific article; zbMATH DE number 4173000
• A polynomial algorithm for recognizing bounded cutwidth in hypergraphs

Cited in

(32)

• Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
• Derivation of algorithms for cutwidth and related graph layout parameters
• Cutwidth: obstructions and algorithmic aspects
• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• Multistart search for the cyclic cutwidth minimization problem
• 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
• Imbalance is fixed parameter tractable
• Typical sequences revisited -- computing width parameters of graphs
• A variable neighbourhood search approach to the cutwidth minimization problem
• The point-set embeddability problem for plane graphs
• On cutwidth parameterized by vertex cover
• Fixed-parameter tractability of treewidth and pathwidth
• Computing the cutwidth of bipartite permutation graphs in linear time
• scientific article; zbMATH DE number 1760009 (Why is no real title available?)
• Confronting intractability via parameters
• The structure of graphs not admitting a fixed immersion
• On cutwidth parameterized by vertex cover
• scientific article; zbMATH DE number 1875430 (Why is no real title available?)
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Optimizing tree decompositions in MSO
• Computing Tree Decompositions
• A linear fixed parameter tractable algorithm for connected pathwidth
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Edge-treewidth: algorithmic and combinatorial properties
• Edge-maximal graphs with cutwidth at most three
• The treewidth of line graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5462384)