Paper Info
Title
An O(n log n) Algorithm for Finding Minimal Path Cover in Circular-Arc Graphs.
Abstract
Whether there exists a polynomial algorithm for the minimal path cover problem in circular-arc graphs remains open. In this paper, we present a polynomial time algorithm for finding a minimal path cover for a set of n arcs in a circular-arc model. Our algorithm takes &Ogr;(nlogn) time.
Year
DOI
Venue
1993
10.1145/170791.170879
ACM Annual Conference on Computer Science (CSC)
Field
DocType
Citations 
Graph,Arc (geometry),Existential quantification,Computer science,Algorithm,Polynomial algorithm,Time complexity,Longest path problem,Path cover
Conference
3
PageRank 
References 
Authors
0.39
4
2
Name
Order
Citations
PageRank
Y. Daniel Liang115314.93
Glenn K. Manacher220598.95