A linear algorithm for the Hamiltonian completion number of the line graph of a tree

DOI10.1016/S0020-0190(00)00164-2zbMath0998.68219WikidataQ126550363 ScholiaQ126550363MaRDI QIDQ1603430

Paolo Detti, Dario Pacciarelli, Carlo Meloni, Alessandro Agnetis

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

treealgorithmsline graphHamiltonian pathHamiltonian completion number

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

Evolutionary operators for the Hamiltonian completion problem ⋮ A lower bound on the Hamiltonian path completion number of a line graph ⋮ Cutting stock with no three parts per pattern: work-in-process and pattern minimization ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ Hamiltonian completions of sparse random graphs

Cites Work

• Unnamed Item
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• The edge Hamiltonian path problem is NP-complete
• A linear algorithm for the Hamiltonian completion number of a tree
• Set-up coordination between two stages of a supply chain
• A result on Hamiltonian line graphs involving restrictions on induced subgraphs

This page was built for publication: A linear algorithm for the Hamiltonian completion number of the line graph of a tree