Faster Exact Bandwidth

DOI10.1007/978-3-540-92248-3_10zbMath1202.05135OpenAlexW2168800311MaRDI QIDQ5302047

Marek Cygan, Marcin Pilipczuk

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_10

zbMATH Keywords

bandwidth algorithm

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Bandwidth and distortion revisited ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs ⋮ An exact algorithm for minimum distortion embedding ⋮ Exact and approximate bandwidth ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth

Cites Work

• Unnamed Item
• Approximating the bandwidth via volume respecting embeddings
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization

This page was built for publication: Faster Exact Bandwidth