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

cutwidthfinite state automatalayout parametersmodified cutwidthparameterized algorithmspathwidth

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

• 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
• 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?)
• 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

(17)

• Cutwidth: obstructions and algorithmic aspects
• Linear layouts measuring neighbourhoods in graphs
• Typical sequences revisited -- computing width parameters of graphs
• Fixed-parameter tractability of treewidth and pathwidth
• Cutwidth: obstructions and algorithmic aspects
• Confronting intractability via parameters
• Linear layouts in submodular systems
• A linear fixed parameter tractable algorithm for connected pathwidth
• Parameterization of tensor network contraction
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Edge-treewidth: algorithmic and combinatorial properties
• Order Reconfiguration under Width Constraints
• Highly connected Steiner subgraph: parameterized algorithms and applications to hitting set problems
• The treewidth of line graphs
• Exact and heuristic computation of the scanwidth of directed acyclic graphs

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)