A polynomial algorithm for recognizing bounded cutwidth in hypergraphs

DOI10.1007/BF02090388zbMath0717.68047MaRDI QIDQ5748885

Zevi Miller, Ivan Hal Sudborough

Publication date: 1991

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

zbMATH Keywords

polynomial algorithmNP-completecutwidth

Mathematics Subject Classification ID

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

Related Items

Cutwidth of triangular grids ⋮ Myhill-Nerode Methods for Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• The vertex separation and search number of a graph
• Graph minors. XIII: The disjoint paths problem
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• The Backboard Wiring Problem: A Placement Algorithm
• On the Cutwidth and the Topological Bandwidth of a Tree
• Topological Bandwidth
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• A polynomial algorithm for the min-cut linear arrangement of trees
• The complexity of searching a graph
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• The NP-completeness column: An ongoing guide