Given a set of terminal pairs on the external face of a planar graph with unit edge weights, we give a linear-time algorithm to compute a set of non-crossing shortest paths joining each terminal pair, if it exists.
Multi-Terminal Shortest Paths in Unit-Weight Planar Graphs in Linear Time / Balzotti, Lorenzo; Franciosa, Paolo G.. - (2021). [10.48550/arXiv.2102.10892]
Multi-Terminal Shortest Paths in Unit-Weight Planar Graphs in Linear Time
Lorenzo Balzotti;Paolo G. Franciosa
2021
Abstract
Given a set of terminal pairs on the external face of a planar graph with unit edge weights, we give a linear-time algorithm to compute a set of non-crossing shortest paths joining each terminal pair, if it exists.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
