Name
Abstract | ||
|---|---|---|
The longest path problem is a generalization of the well known Hamiltonian path problem. It has been shown that the longest path problem is NP-complete. Many researchers try to solve it on some special classes of graphs. Another practical generalization is given two vertices and tries to find a longest path between these two vertices. It is called the end-to-end longest path problem. In this paper, we consider this general problem on a mesh. We generalize a previous work to solve the problem on meshes with one missing vertex in linear time. Further research opportunities and improvements are also suggested. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.3233/978-1-61499-484-8-59 | Frontiers in Artificial Intelligence and Applications |
Keywords | Field | DocType |
Rectangular Grid Graph,Mesh,Longest Path,Hamiltonian Path | Discrete mathematics,Shortest path problem,Vertex (geometry),End-to-end principle,Computer science,Vertex (graph theory),Parallel computing,Longest path problem | Conference |
Volume | ISSN | Citations |
274 | 0922-6389 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ting-Wei Chang | 1 | 24 | 5.30 |
| Ondrej Navrátil | 2 | 0 | 0.34 |
| Sheng-Lung Peng | 3 | 3 | 4.10 |