Algorithms for optimal orientations of a unicyclic graph

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for optimal orientations of a unicyclic graph

Full text

Pdf (571 KB)

Source

ACM Southeast Regional Conference archive
Proceedings of the 42nd annual Southeast regional conference table of contents

Huntsville, Alabama

SESSION: Theory table of contents

Pages: 219 - 223

Year of Publication: 2004

ISBN:1-58113-870-9

Authors

Suk Jai Seo	Middle Tennessee State University, Murfreesboro, TN
Ashok T. Amin	University of Alabama in Huntsville, Huntsville, AL

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 1

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

ABSTRACT

Let (G, R) denote the directed graph obtained from undirected graph G by an acyclic orientation R so that (G, R) contains no directed cycle. We consider acyclic orientations R of a unicyclic graph G which maximizes/minimizes the number of ordered pairs of non-adjacent vertices with directed paths in (G, R). These orientations are referred as optimal orientations. We present algorithms to determine optimal orientations of a unicyclic graph.

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. S. Anderson and F. Harary, Trees and unicyclic graphs. Mathematics Teacher. 60(1967), pp. 145--348.
	2	Béla Bollobás and M. Rosenfeld, Sorting in One Round. Israel J. of Math. 38 (1981), pp. 154--160.
	3	O. Chan, C. C. Chen, and P. J. Slater, On a Characterization of Comparability Graphs. Ars Combinatoria 23A (1987) pp. 67--79.
	4	Gary Chartrand , Linda Lesniak, Graphs & digraphs (2nd ed.), Wadsworth Publ. Co., Belmont, CA, 1986
	5	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
	6	S. Louis Hakimi , Edward F. Schmeichel , Neal E. Young, Orienting graphs to optimize reachability, Information Processing Letters, v.63 n.5, p.229-235, Sept. 15, 1997 [doi>10.1016/S0020-0190(97)00129-4]
	7	F. Harary, Graph Theory. Addison-Wesley, Reading, MA (1969).
	8	H. E. Robbins, A Theorem on Graphs with an Application to a Problem of Traffic Control, Amer. Math. Monthly 46 (1939), pp. 281--283.
	9	Suk Jai Seo, On Optimal Acyclic Orientations of a Graph. A Ph.D Dissertation, University of Alabama in Huntsville (2001).
	10	Suk Jai Seo and A. T. Amin, On extremal Oriented Trees. Congressus Numerantium (2001).
	11	H. Wang and A. T. Amin, On Optimal Acyclic Orientations of a Graph. Congressus Numerantium 137 (1999), pp. 121--128.