A polynomial algorithm for recognizing bounded cutwidth in hypergraphs

DOI10.1007/BF02090388MaRDI QIDQ5748885zbMATH OpenFDO

Authors Z. Miller, I. H. Sudborough

Publication date 1991

Published in Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

NP-completepolynomial algorithmcutwidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)

Recommendations

• scientific article; zbMATH DE number 3958752
• scientific article; zbMATH DE number 1875430
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Computing the cutwidth of bipartite permutation graphs in linear time

Cites work

• scientific article; zbMATH DE number 3813518 (Why is no real title available?)
• scientific article; zbMATH DE number 4064479 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• A polynomial algorithm for the min-cut linear arrangement of trees
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• On the Cutwidth and the Topological Bandwidth of a Tree
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• The Backboard Wiring Problem: A Placement Algorithm
• The NP-completeness column: An ongoing guide
• The complexity of searching a graph
• The vertex separation and search number of a graph
• Topological Bandwidth

Cited in

(8)

• Cutwidth of triangular grids
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
• scientific article; zbMATH DE number 1875430 (Why is no real title available?)
• The cutwidth and the vertex separation number of hypergraphs and their König’s representations
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• scientific article; zbMATH DE number 6850403 (Why is no real title available?)
• Algorithms for the determination of cutsets in a hypergraph
• scientific article; zbMATH DE number 3958752 (Why is no real title available?)

This page was built for publication: A polynomial algorithm for recognizing bounded cutwidth in hypergraphs

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