Finding shortest non-trivial cycles in directed graphs on surfaces
Let $D$ be a weighted directed graph cellularly embedded in a surface of genus $g$, orientable or not, possibly with boundary. We describe algorithms to compute shortest non-contractible and shortest surface non-separating cycles in $D$, generalizing previous results that dealt with undirected grap...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2016-04-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/225 |