Name
Abstract | ||
|---|---|---|
We consider the problem of finding a shortest closed walk (SEW) or cycle (SEC) surrounding a given obstacle O in the plane and chosen from a nonnegatively weighted graph G with a fixed (not necessarily planar) embedding in the plane. We show that SEW is polynomial if O is connected and NP-hard otherwise, that SEC is polynomial when O is a topological ball and NP-hard if O is a general connected region, and that both SEW and SEC are polynomial for general O when G has a plane layout. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1016/0020-0190(89)90129-4 | Inf. Process. Lett. |
Keywords | Field | DocType |
embedded graph | Graph,Discrete mathematics,Combinatorics,Embedding,Polynomial,Planar,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 3 | 0020-0190 |
Citations | PageRank | References |
5 | 0.69 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Scott Provan | 1 | 678 | 90.11 |