2015 | OriginalPaper | Chapter
A Unified Approach for the Longest Path Problem on Some Tree-Like Graphs
Authors : Ang-Lin Dong, Sheng-Lung Peng
Published in: New Information and Communication Technologies for Knowledge Management in Organizations
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In a graph, a maximal biconnected component is called a block. A graph is called a block (resp., cactus and probe block) graph if its every block is a clique (resp., an edge or cycle, and complete split graph). In this paper, we propose a unified approach for the longest path problem on block, cactus, and probe block graphs. As a result, the longest path problem can be solved in linear time on block and probe block graphs, and in quadrat time on cactus graphs.