Derivation of algorithms for cutwidth and related graph layout parameters

DOI10.1016/J.JCSS.2008.10.003MaRDI QIDQ1015810zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos

Publication date 30 April 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/22002

zbMATH Keywords

pathwidthparameterized algorithmsfinite state automatacutwidthlayout parametersmodified cutwidth

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Recommendations

• Mathematical Foundations of Computer Science 2003
• Cutwidth: obstructions and algorithmic aspects
• Cutwidth: obstructions and algorithmic aspects
• Cutwidth I: A linear time fixed parameter algorithm
• Linear layouts in submodular systems

Cites work

• scientific article; zbMATH DE number 5605062 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 176761 (Why is no real title available?)
• scientific article; zbMATH DE number 1301106 (Why is no real title available?)
• scientific article; zbMATH DE number 1303600 (Why is no real title available?)
• scientific article; zbMATH DE number 475614 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 841653 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Constructive linear time algorithms for branchwidth
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Graph minors. I. Excluding a forest
• Mathematical Foundations of Computer Science 2003
• Min Cut is NP-complete for edge weighted trees
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• The vertex separation number of a graph equals its path-width

Cited in

(15)

• Cutwidth: obstructions and algorithmic aspects
• The treewidth of line graphs
• A linear fixed parameter tractable algorithm for connected pathwidth
• Mathematical Foundations of Computer Science 2003
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Edge-treewidth: algorithmic and combinatorial properties
• scientific article; zbMATH DE number 7559371 (Why is no real title available?)
• Confronting intractability via parameters
• Order Reconfiguration under Width Constraints
• Cutwidth: obstructions and algorithmic aspects
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Linear layouts measuring neighbourhoods in graphs
• Linear layouts in submodular systems
• Typical sequences revisited -- computing width parameters of graphs
• Fixed-parameter tractability of treewidth and pathwidth

This page was built for publication: Derivation of algorithms for cutwidth and related graph layout parameters

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