𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

✍ Scribed by Takao Nishizeki; Takao Asano; Takahiro Watanabe

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
760 KB
Volume
5
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An upper bound on the length of a Hamilt
An upper bound on the length of a Hamiltonian walk of a maximal planar graph
✍ Takao Asano; Takao Nishizeki; Takahiro Watanabe πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 840 KB

## Abstract A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with __p__(β‰₯ 3) vertices has a Hamiltonian c

Linear-time certifying algorithms for th
Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
✍ Ruo-Wei Hung; Maw-Shang Chang πŸ“‚ Article πŸ“… 2011 πŸ› Elsevier Science 🌐 English βš– 252 KB

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appear