Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
From MaRDI portal
Publication:1978696
DOI10.1016/S0304-3975(99)00181-4zbMATH Open0947.90083OpenAlexW2069380066MaRDI QIDQ1978696FDOQ1978696
Goran Konjevod, Avrim Blum, Santosh S. Vempala, R. Ravi
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00181-4
Recommendations
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- Semidefinite relaxations of ordering problems
- On semidefinite programming bounds for graph bandwidth
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- scientific article; zbMATH DE number 2119717
- Semidefinite programming relaxations for the graph partitioning problem
- scientific article; zbMATH DE number 2196288
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization
- Title not available (Why is that?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The NP-completeness of the bandwidth minimization problem
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Complexity Results for Bandwidth Minimization
- The bandwidth problem for graphs and matrices—a survey
- Title not available (Why is that?)
- A remark on a problem of Harary
- Graphs with small bandwidth and cutwidth
- Title not available (Why is that?)
- Bandwidth Minimization: An approximation algorithm for caterpillars
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
Cited In (12)
- An exponential time 2-approximation algorithm for bandwidth
- Lower bounds for the bandwidth problem
- Title not available (Why is that?)
- Retracting Graphs to Cycles
- A branch and bound algorithm for the matrix bandwidth minimization
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Interval degree and bandwidth of a graph
- Flow metrics
- Convex Relaxations for Permutation Problems
- Matrix Relaxations in Combinatorial Optimization
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
This page was built for publication: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978696)
