Bandwidth contrained NP-complete problems

DOI10.1016/0304-3975(85)90068-4zbMath0618.68043OpenAlexW2039247498MaRDI QIDQ1822500

Ivan Hal Sudborough, Burkhard Monien

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90068-4

zbMATH Keywords

NP-completenessgraph algorithms

Mathematics Subject Classification ID

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

Related Items (8)

On problems with short certificates ⋮ Nonserial dynamic programming formulations of satisfiability ⋮ Unnamed Item ⋮ Factoring a band matrix over a semiring ⋮ Bandwidth and pebbling ⋮ Revising Johnson's table for the 21st century ⋮ Complete problems for space bounded subclasses of NP ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth constraints on problems complete for polynomial time
• Complete problems for space bounded subclasses of NP
• The NP-completeness of the bandwidth minimization problem
• Relationships between nondeterministic and deterministic tape complexities
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Edge-Deletion Problems
• The bandwidth problem for graphs and matrices—a survey
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization
• The complexity of satisfiability problems
• On the completeness of a generalized matching problem
• On Languages Accepted in Polynomial Time

This page was built for publication: Bandwidth contrained NP-complete problems