A linear algorithm for the Hamiltonian completion number of a tree

DOI10.1016/0020-0190(76)90080-6zbMath0327.05104OpenAlexW2022016054MaRDI QIDQ1226105

Sukhamay Kundu

Publication date: 1976

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

Full work available at URL: https://doi.org/10.1016/0020-0190(76)90080-6

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Algorithms in computer science (68W99)

Related Items (7)

Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ The total interval number of a tree and the Hamiltonian completion number of its line graph ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ The approximability of the weighted Hamiltonian path completion problem on a tree ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a tree

Cites Work

• Optimal chain partitions of trees
• Parallel concepts in graph theory
• A Linear Tree Partitioning Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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