Bandwidth Minimization: An approximation algorithm for caterpillars

DOI10.1007/BF02090396zbMATH Open0767.68081MaRDI QIDQ3979607FDOQ3979607

Authors:

Publication date: 26 June 1992

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

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

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)

Cites Work

• Title not available (Why is that?)
• The NP-completeness of the bandwidth minimization problem
• 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 of Caterpillars with Hairs of Length 1 and 2
• Complexity Results for Bandwidth Minimization
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars
• Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Minimizing the bandwidth of sparse symmetric matrices
• Bandwidth constraints on problems complete for polynomial time

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)