Maier, Markus; Mecke, Steffen; Wagner, Dorothea 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]. Cited in 1 Document 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 \textit{M. Maier} et al., Lect. Notes Comput. Sci. 4362, 410--421 (2007; Zbl 1131.68330) Full Text: DOI