Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420461 | Discrete Applied Mathematics | 2009 | 5 Pages |
Abstract
A cycle in a graph GG is isometric if the distance between two vertices in the cycle is equal to their distance in GG. Finding the longest isometric cycle of a graph is then a natural variant of the problem of finding a longest cycle. While most variants of the longest cycle problem are NP-complete, we show that quite surprisingly, one can find a longest isometric cycle in a graph in polynomial time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Lokshtanov,