Bandwidth Minimization: An approximation algorithm for caterpillars

DOI10.1007/BF02090396zbMath0767.68081MaRDI QIDQ3979607

No author found.

Publication date: 26 June 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmcaterpillarsbandwidth minimization problemlevel algorithms

Mathematics Subject Classification ID

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

Related Items

Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars ⋮ Approximating the bandwidth of caterpillars ⋮ Graph bandwidth of weighted caterpillars ⋮ Embedding ladders and caterpillars into the hypercube ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems ⋮ Approximation algorithms for the bandwidth minimization problem for a large class of trees ⋮ Bandwidth of Bipartite Permutation Graphs in Polynomial Time ⋮ 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 ⋮ Bandwidth of bipartite permutation graphs in polynomial time

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