An optimal algorithm for finding biconnected components in permutation graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal algorithm for finding biconnected components in permutation graphs

Full text

Pdf (475 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 1995 ACM 23rd annual conference on Computer science table of contents

Nashville, Tennessee, United States

Pages: 104 - 108

Year of Publication: 1995

ISBN:0-89791-737-5

Authors

Y. Daniel Liang	Department of Computer Science, Indiana Purdue University at Fort Wayne, Fort Wayne, IN
Chongkye Rhee	Department of Mathematics, Statistics and Computer Science, Eastern Kentucky University, Richmond, KY

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 26, Citation Count: 1

Additional Information:

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/259526.259544 What is a DOI?

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	M.J. Atallah and S. R. Kosaraju, An efficient algorithm {or rnaxdominance, with applications, Algorithmica, 4 { 1989) 221-236.
	2	Mikhail J. Atallah , Glenn K. Manacher , J. Urrutia, Finding a minimum independent dominating set in a permutation graph, Discrete Applied Mathematics, v.21 n.3, p.177-183, October 1988 [doi>10.1016/0166-218X(88)90064-9]
	3	Andreas Brandstädt , Dieter Kratsch, On domination problems for permutation and other graphs, Theoretical Computer Science, v.54 n.2-3, p.181-198, Oct. 1987 [doi>10.1016/0304-3975(87)90128-9]
	4	C.J. Colbourn, J. M. Keil and L. K. Stewart, Finding minimum dominating cycles in permutation graphs, Operations Research Letter 4 (1985) 13-17.
	5	M. Farber and J. M. Keil, Domination in permutation graphs, J. ofAigo. 6 (1985) 309-321.
	6	M.C. Golumbic, Algorithmic Graph Theor3, and Perfect Graphs, Academic Press, New York, 1980.
	7	Dorit S. Hochbaum, Why should biconnected components be identified first, Discrete Applied Mathematics, v.42 n.2-3, p.203-210, April 27, 1993 [doi>10.1016/0166-218X(93)90046-Q]
	8	Y. Liang , C. Rhee , S. K. Dhall , S. Lakshmivarahan, A new approach for the domination problem on permutation graphs, Information Processing Letters, v.37 n.4, p.219-224, Feb. 28, 1991 [doi>10.1016/0020-0190(91)90192-K]
	9	A. Pnueli, A. Lempel and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canadian J. of Math. 23 ( 1971) 160-175.
	10	C. Rhee , Y. Daniel Liang , S. K. Dhall , S. Lakshmivarahan, Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs, Information Processing Letters, v.49 n.1, p.45-50, Jan. 14, 1994 [doi>10.1016/0020-0190(94)90053-1]
	11	C. Rhee , Y. D. Liang , S. K. Dhall , S. Lakshmivarahan, An $O(N + M)$-Time Algorithm for Finding a Minimum-WeightDominating Set in a Permutation Graph, SIAM Journal on Computing, v.25 n.2, p.404-419, February 1996 [doi>10.1137/S0097539794200383]
	12	J. Spinrad, On comparability and permutation graphs, SIAM J. Computing, 14 (1985) 658-670.
	13	Kuo-Hui Tsai , Wen-Lian Hsu, Fast algorithms for the dominating set problem on permutation graphs, Proceedings of the international symposium on Algorithms, p.109-117, August 1990, Tokyo, Japan