On Computing Longest Paths in Small Graph Classes
スポンサーリンク
概要
- 論文の詳細を見る
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.
- World Scientific Publishingの論文
- 2007-10-00
World Scientific Publishing | 論文
- LASER LIGHT CONTROL OF SELF-ORGANIZATION PROCESS
- Irreversible Investment, Operating Flexibility, and Time Lags
- Outcome Uncertainty and Interestedness in Game-Playing : A Case Study using Synchronized Hex
- Probability Distribution Functional for Equal-time Correlation Functions in Curved Space
- On Computing Longest Paths in Small Graph Classes