Bandwidth Minimization: An approximation algorithm for caterpillars
From MaRDI portal
Publication:3979607
DOI10.1007/BF02090396zbMath0767.68081MaRDI QIDQ3979607
No author found.
Publication date: 26 June 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Approximation algorithms for the bandwidth minimization problem for a large class of trees, Graph bandwidth of weighted caterpillars, Bandwidth of bipartite permutation graphs in polynomial time, Embedding ladders and caterpillars into the hypercube, Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998, Approximating the bandwidth via volume respecting embeddings, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Approximating the bandwidth of caterpillars
Cites Work
- Unnamed Item
- Bandwidth constraints on problems complete for polynomial time
- The NP-completeness of the bandwidth minimization problem
- Minimizing the bandwidth of sparse symmetric matrices
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- The bandwidth problem for graphs and matrices—a survey
- The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
- Complexity Results for Bandwidth Minimization
