Parallel Computation for the Bandwidth Minimization Problem

Khoa T. Vo () and Gerhard Reinelt ()
Additional contact information
Khoa T. Vo: Institute of Computer Science, University of Heidelberg
Gerhard Reinelt: Institute of Computer Science, University of Heidelberg

Chapter 78 in Operations Research Proceedings 2008, 2009, pp 481-486 from Springer

Abstract: Summary The bandwidth minimization problem is a classical combinatorial optimization problem that has been studied since around 1960. It is formulated as follows. Given a connected graph G = (V;E) with n nodes and m edges, find a labeling π, i.e. a bijection between V and {1; 2;… ; n}, such that the maximum difference |π(u)–(v)|, uv ε E, is minimized. This problem is NP-hard even for binary trees [3]. Though much work on the bandwidth problem has been done, the gaps between best known lower and upper bounds for benchmark problems is still large. Applications of the bandwidth problem can be found in many areas: solving systems of linear equations, data storing, electronic circuit design, and recently in topology compression of road networks [7]. Due to the hardness of bandwidth minimization, much research has dealt with heuristic methods. These range from structured methods to metaheuristic methods, genetic algorithm and scatter search. The reader can refer to [1] for detailed references in this areas. For solving the problem to optimality, dynamic programming and branch-andbound have been used but with little success for sparse graphs. Caprara and Salazar [2] have proposed new lower bounds and strong integer linear programming (ILP) formulations to compute the bounds more effectively. Their method is therefore used in our parallel implementation documented in this paper. We will report about computational results for problem instances with up to 200 nodes.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-00142-0_78

Ordering information: This item can be ordered from
http://www.springer.com/9783642001420

DOI: 10.1007/978-3-642-00142-0_78

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().