Advances on the Hamiltonian Completion Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Advances on the Hamiltonian Completion Problem

Full text

Pdf (607 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 3 (July 1975) table of contents

Pages: 352 - 360

Year of Publication: 1975

ISSN:0004-5411

Authors

S. E. Goodman	Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA
S. T. Hedetniemi	Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA
P. J. Slater	National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, Iowa

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/321892.321897 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	KARP, R.M. Reducibility among combinatorial problems. In Complexily of Computer Computatio~s, R. Miller and J. Thatcher, Eds., Plenum, New York, 1972, pp. 85-103.
	2	KNUTH, D.E. Fundamenlal Algorilhms. Addison-Wesley, Reading, Mass., 1969, pp. 334-337.
	3	BOESCH, F. T., CREN, S., AND McHu~H, J. A.M. On covering the points of a graph with point disjoint paths. In Graphs and Combinatorics, R. A. Bari and F. Harary, Eds., Springer-Verlag, Berlin, 1974, pp. 201-212.
	4	GOODMAN, S., AND HEDETNIEMI, S. On the Hamiltonian completion problem. In Graphs and Combinatorics, R. A. Bari and F. Harary, Eds., Springer-Verlag, Berlin, 1974, pp. 262-272.
	5	GOODMAN, S., AND HEDETNIEMI, S. A linear algorithm for the Hamiltonian completion problem for trees. (Submitted for publication.)
	6	CHATY, G., AND CHEIN, M. Path-invariants in acircuit digraphs. Preprint, 1974.
	7	GOODMAN, S., AND HEDETNIEMI, S. Eulerian walks in graphs. SIAM J. Comput. ~ (1973), 18-27.
	8	GOODMAN, S., AND HEDETNIEMI, S. On Hamiltonian walks in graphs. SIAM J. Comput. $ (1974), 214-221.
	9	HARARY, F., AND SCHWENK, A. Evolution of the path number of a graph, covering and packing in graphs, II. !n Graph Theory and Computing, R. C. Read, Ed., Academic Press, New York, 1972, pp. 39-45. RECEIVED DECEMBER 1973; REVISED OCTOBER 1974

CITED BY 4

	Y. Daniel Liang , G. K. Manacher, An O(nlogn) algorithm for finding minimal path cover in circular-arc graphs, Proceedings of the 1993 ACM conference on Computer science, p.390-397, February 16-18, 1993, Indianapolis, Indiana, United States
	David Gamarnik , Maxim Sviridenko, Hamiltonian completions of sparse random graphs, Discrete Applied Mathematics, v.152 n.1-3, p.139-158, 1 November 2005
	Paolo Detti , Carlo Meloni, A linear algorithm for the Hamiltonian completion number of the line graph of a cactus, Discrete Applied Mathematics, v.136 n.2-3, p.197-215, 15 February 2004
	Quincy Wu , Chin Lung Lu , Richard Chia-Tung Lee, The approximability of the weighted Hamiltonian path completion problem on a tree, Theoretical Computer Science, v.341 n.1, p.385-397, 5 September 2005