An O(nlogn) algorithm for finding minimal path cover in circular-arc graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(nlogn) algorithm for finding minimal path cover in circular-arc graphs

Full text

Pdf (726 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 1993 ACM conference on Computer science table of contents

Indianapolis, Indiana, United States

Pages: 390 - 397

Year of Publication: 1993

ISBN:0-89791-558-5

Authors

Y. Daniel Liang	Department of Computer Science, Indiana Purdue University at Fort Wayne, Fort Wayne, IN
G. K. Manacher	Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/170791.170879 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Rao Arikati , C. Pandu Rangan, Linear algorithm for optimal path cover problem on interval graphs, Information Processing Letters, v.35 n.3, p.149-153, Jul. 1990 [doi>10.1016/0020-0190(90)90064-5]
	2	M.A. Bonuccelli and D. P. Borer, Minimum node-disjoint path covering for circular-arc graphs, Inform. Process. Lea. 8 (1979) 159-161.
	3	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	4	M. C, Golmnhic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
	5	S. E. Goodman , S. T. Hedetniemi , P. J. Slater, Advances on the Hamiltonian Completion Problem, Journal of the ACM (JACM), v.22 n.3, p.352-360, July 1975 [doi>10.1145/321892.321897]
	6	Y. D. Lians, C. Rhee, S. IL Dhall, and S. Lakshmiverahan, an O (nZlogn) algorithm for Hamiltanian path ixoblem in ~-~rc grephs, 29th AIIerton Conf~ 1991.
	7	Y.D. Lian8, G. IC Msnacher; C. Rhee., T. A. Manku~ S. IC DlmIL and S. Lakslunivarahan, an O (n logn) ai~ for finding a Hamilumian paflm and circuit in circular-arc Oapl=, mammcri~ Augtmt, 1992.
	8	G. K. Manacher , T. A. Mankus , C. J. Smith, An optimum &Tgr;(n log n) algorithm for finding a canonical Hamiltonian path and canonical Hamiltonian circuit in a set of intervals, Information Processing Letters, v.35 n.4, p.205-211, Aug. 1990 [doi>10.1016/0020-0190(90)90025-S]
	9	S. Moran and Y. Wolfsmhl, Optimal covering of cacti by vertex-disjoint paths, Tech. Rept., Technion Instimm of TecJmology (1988).
	10	Wei-Kuan Shih , T. C. Chern , Wen-Lian Hsu, An O(n2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs, SIAM Journal on Computing, v.21 n.6, p.1026-1046, Dec. 1992 [doi>10.1137/0221061]

CITED BY 2

	Ruo-Wei Hung , Maw-Shang Chang, Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Discrete Applied Mathematics, v.154 n.1, p.76-105, 1 January 2006
	Yan Meng , Timothy Sherwood , Ryan Kastner, Leakage power reduction of embedded memories on FPGAs through location assignment, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA