Bandwidth Minimization: An approximation algorithm for caterpillars

DOI10.1007/BF02090396MaRDI QIDQ3979607zbMATH OpenFDO

Authors

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)

Recommendations

• Algorithmic Applications in Management
• Graph bandwidth of weighted caterpillars
• Approximation algorithms for the bandwidth minimization problem for a large class of trees
• Improved bandwidth approximation for trees and chordal graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Bandwidth constraints on problems complete for polynomial time
• Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
• Complexity Results for Bandwidth Minimization
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Minimizing the bandwidth of sparse symmetric matrices
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The NP-completeness of the bandwidth minimization problem
• The bandwidth problem for graphs and matrices—a survey

Cited in

(16)

• Bandwidth of bipartite permutation graphs in polynomial time
• Approximating the bandwidth via volume respecting embeddings
• Algorithmic Applications in Management
• Graph bandwidth of weighted caterpillars
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Tractabilities and intractabilities on geometric intersection graphs
• Approximating the bandwidth of caterpillars
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
• Embedding ladders and caterpillars into the hypercube
• Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
• 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
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Approximation algorithms for the bandwidth minimization problem for a large class of trees

This page was built for publication: Bandwidth Minimization: An approximation algorithm for caterpillars

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