We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on disjoint path problems. However, the package is intended to serve as a general framework, wherein algorithms for various problems on planar networks may be integrated and visualized. For this aim, the structure of the package is designed so that integration of new algorithms and even new algorithmic problems amounts to applying a short “recipe”. The package has been used to develop new variations of well-known disjoint path algorithms, which heuristically optimize additional 𝒩𝒫-hard objectives such as the total length of all paths. We will prove that the problem of finding edge-disjoint paths of minimum total length in a planar graph is 𝒩𝒫-hard, even if all terminals lie on the outer face, the Eulerian condition is fulfilled, and the maximum degree is four. Finally, as a demonstration how PlaNet can be used as a tool for developing new heuristics for 𝒩𝒫-hard problems, we will report on results of experimental studies on efficient heuristics for this problem
Keywords for this software
References in zbMATH (referenced in 4 articles , 1 standard article )
Showing results 1 to 4 of 4.
- Oellrich, Martin: Minimum cost disjoint paths under arc dependences. Algorithms for practice. (2008)
- Zhang, Peng; Zhao, Wenbo: On the complexity and approximation of the Min-Sum and Min-Max Disjoint Paths problems (2007)
- Müller, E.; Horbach, S.; Ackermann, J.; Schütze, J.; Baum, H.: Production system planning in competence-cell-based networks (2006)
- Brandes, Ulrik; Schlickenrieder, Wolfram; Neyer, Gabriele; Wagner, Dorothea; Weihe, Karsten: A software package of algorithms and heuristics for disjoint paths in \itPlanar \itNetworks (1999)