Name
Abstract | ||
|---|---|---|
Gavril [F. Gavril, Algorithms for maximum weight induced paths, Information Processing Letters 81 (2002) 203–208] showed that the length of a longest induced path for graphs having no induced cycles on more than k vertices can be computed in O(nkm) time where n and m denote the number of vertices and edges, respectively. In this paper, we present an O(nk) time algorithm for the same problem. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2008.01.019 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
k-chordal graph,Longest induced path problem | Journal | 156 |
Issue | ISSN | Citations |
15 | 0166-218X | 2 |
PageRank | References | Authors |
0.41 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tetsuya Ishizeki | 1 | 2 | 0.41 |
| Yota Otachi | 2 | 161 | 37.16 |
| Koichi Yamazaki | 3 | 222 | 21.85 |