Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow

DOI10.1017/S1446181100013894zbMath1009.05088OpenAlexW2169473633MaRDI QIDQ4796447

Arundhati Raychaudhuri, D. S. Franzblau

Publication date: 11 April 2003

Published in: The ANZIAM Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s1446181100013894

zbMATH Keywords

treeHamiltonian pathminimum path coverlinear time algorithm for tree maximum flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Evolutionary operators for the Hamiltonian completion problem, Parameterizing path partitions, An improved approximation algorithm for the minimum 3-path partition problem, A survey of parameterized algorithms and the complexity of edge modification, Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphs, On island sequences of labelings with a condition at distance two, Nontrivial path covers of graphs: existence, minimization and maximization, A local search 4/3-approximation algorithm for the minimum 3-path partition problem, Evolving test instances of the Hamiltonian completion problem

Cites Work

• On mapping processes to processors in distributed systems
• Optimal covering of cacti by vertex-disjoint paths
• A linear algorithm for the Hamiltonian completion number of a tree
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Advances on the Hamiltonian Completion Problem
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• Unnamed Item
• Unnamed Item