Name
Abstract | ||
|---|---|---|
The longest path problem is the one that finds a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. Among those, for trees, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for some tree-like graph classes by this approach. We next propose two new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on these classes. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1142/S0129054107005054 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
algorithmic graph theory, design and analysis of algorithms, graph classes, longest path problem | Discrete mathematics,Combinatorics,Path (graph theory),Shortest path problem,Graph property,Hamiltonian path,Hamiltonian path problem,Longest path problem,Mathematics,Widest path problem,Path graph | Journal |
Volume | Issue | ISSN |
18 | 5 | 0129-0541 |
Citations | PageRank | References |
26 | 1.07 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryuhei Uehara | 1 | 528 | 75.38 |
| yushi uno | 2 | 222 | 28.80 |