An optimal algorithm for finding depth-first spanning tree on permutation graphs |
| |
Authors: | Sukumar Mondal Madhumangal Pal Tapan K. Pal |
| |
Affiliation: | 1. Department of Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore-721 102, West Bengal, India 2. Department of Mathematics, Midnapore College, Midnapore-721 101, West Bengal, India
|
| |
Abstract: | LetG be a connected graph ofn vertices. The problem of finding a depth-first spanning tree ofG is to find a connected subgraph ofG with then vertices andn − 1 edges by depth-first-search. In this paper, we propose anO(n) time algorithm to solve this problem on permutation graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|