Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
From MaRDI portal
Publication:4796447
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
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