Coping with the NP-hardness of the graph bandwidth problem

DOI10.1007/3-540-44985-X_2MaRDI QIDQ2721963zbMATH OpenFDO

Authors Uriel Feige

Publication date 11 July 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44985-X_2

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(21)

• Bandwidth of bipartite permutation graphs in polynomial time
• The online graph bandwidth problem
• Interval degree and bandwidth of a graph
• Tractabilities and intractabilities on geometric intersection graphs
• Bandwidth contrained NP-complete problems
• Capacitated domination faster than O(2ⁿ)
• Grid drawings of graphs with constant edge-vertex resolution
• Approximating the bandwidth of caterpillars
• An exponential time 2-approximation algorithm for bandwidth
• An exponential time 2-approximation algorithm for bandwidth
• Bandwidth and distortion revisited
• Faster Exact Bandwidth
• An exact algorithm for minimum distortion embedding
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Hardness results for approximating the bandwidth
• Ordering transactions with bounded unfairness: definitions, complexity and constructions
• Exact and parameterized algorithms for window width minimization in bipartite arrangement
• Exact and approximate digraph bandwidth
• Exact and approximate bandwidth
• Exact and parameterized algorithms for window width minimization in bipartite arrangement
• Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing

This page was built for publication: Coping with the NP-hardness of the graph bandwidth problem

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