×

Algorithmic aspects of minimum energy edge-disjoint paths in wireless networks. (English) Zbl 1131.68330

van Leeuwen, Jan (ed.) et al., SOFSEM 2007: Theory and practice of computer science. 33rd conference on current trends in theory and practice of computer science, Harrachov, Czech Republic, January 20–26, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-69506-6/pbk). Lecture Notes in Computer Science 4362, 410-421 (2007).
Summary: The problem of finding \(k\) minimum energy, edge-disjoint paths in wireless networks (MEEP) arises in the context of routing and belongs to the class of range assignment problems. A polynomial algorithm which guarantees a factor-\(k\)-approximation for this problem has been presented before, but its complexity status was open. In this paper we prove that MEEP is NP-hard and give new lower and upper bounds on the approximation factor of the \(k\)-approximation algorithm. For MEEP on acyclic graphs we introduce an exact, polynomial algorithm which is then extended to a heuristic for arbitrary graphs.
For the entire collection see [Zbl 1129.68007].

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms

Software:

MEEP
PDFBibTeX XMLCite
Full Text: DOI