Advances on the Hamiltonian Completion Problem

DOI10.1145/321892.321897zbMath0307.05123OpenAlexW2090154053MaRDI QIDQ4063184

S. Goodman, Stephen T. Hedetniemi, Peter J. Slater

Publication date: 1975

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321892.321897

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Graph theory (05C99)

Related Items (11)

Combinatorial algorithms on a class of graphs ⋮ Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow ⋮ On the Hamiltonian number of a plane graph ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ Linear algorithm for optimal path cover problem on interval graphs ⋮ The Turán number for spanning linear forests ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Path coverings of the vertices of a tree ⋮ The approximability of the weighted Hamiltonian path completion problem on a tree ⋮ Atoll decompositions of graphs ⋮ Hamiltonian completions of sparse random graphs

This page was built for publication: Advances on the Hamiltonian Completion Problem