An O(p^3) Algorithm for Finding Hamiltonian Cycles in Certain Digraphs
スポンサーリンク
概要
- 論文の詳細を見る
The problem for finding a directed hamiltonian cycle in a digraph is one of the NP-complete problems. No nontrivial necessary and sufficient condition for a digraph to have a directed hamiltonian cycle has been obtained. Only some sufficient conditions have been obtained. One of the strongest sufficient conditions was obtained by Meyniel. He proved that a strict diconnected digraph with p vertices has a directed hamiltonian cycle if d(u)+d(v)≥2p-1 for any pair of nonadjacent vertices u and v (where d(v) is the number of arcs incident to v). In this paper we give an efficient algorithm for finding a directed hamiltonian cycle in a digraph satisfying Meyniel's condition. For a digraph with p vertices our algorithm finds a directed hamiltonian cycle in O(p^3) time. Our algorithm is based on the new proof technique of Meyniel's theorem given by Bondy and Thomassen.
- 一般社団法人情報処理学会の論文
- 1980-08-31
著者
-
Saito N
Department Of Chemistry Nagaoka University Of Technology
-
Takamizawa K
Department Of Applied Physics Faculty Of Engineering Kyushu University
-
Takamizawa K
Department Of Electrical Communications Faculty Of Engineering Tohoku University
-
NISHIZEKI T
Department of Electrical Communications, Faculty of Engineering, Tohoku University
-
Nishizeki T
Department Of Electrical Communications Faculty Of Engineering Tohoku University
関連論文
- Highly-Soluble Fluorocarbon Surfactant in Supercritical Carbon Dioxide: Effect of Counter Cation on Solubility
- Overall Water Splitting by RuO_2-loaded Hexagonal YInO_3 with a Distorted Trigonal Bipyramid
- Overall Water Splitting by RuO_2-dispersed Divalent-ion-doped GaN Photocatalysts with d^ Electronic Configuration
- Remarkable Support Effects of Gallium Compounds on the Activity and Selectivity of Ru Metal Catalyst for Liquid-phase Citral Hydrogenation
- RuO_2-loaded Sr^-doped CeO_2 with d^0 Electronic Configuration as a New Photocatalyst for Overall Water Splitting
- Photocatalytic Activity of RuO_2-loaded Pb_xWO_4 (x = 0.2-1.1) for Water Decomposition
- A New Photocatalyst of RuO_2-loaded PbWO_4 for Overall Splitting of Water
- Photocatalytic Activity for Water Decomposition of RuO_2-Loaded SrIn_2O_4 with d^ Configuration
- Hydrogenation of Solid State Carbonates
- Chemical and Electrochemical Preparation of Poly(quinoline-2,6-diyl), Poly(quinoxaline-2,6-diyl), and Poly(1,5-naphthyridine-2,6-diyl)by Using Nickel Complexes. Importance of the 2,6-Bonding for Linear Structure, Highly Extended π-Conjugation, and Strong
- Preparation and Properties of Highly Electron-accepting Poly(pyrimidine-2,5-diyl)
- Synthesis of Tungstate Thin Films and Their Optical Properties
- Synthesis of Ultra Pure Long Normal Alkanes to Hexacohectane, Their Crystallization and Tehrmal Behavior
- EFFECTS OF 5-FLUOROURACIL ON CARDIAC FUNCTION AND METABOLISM IN ISOLATED PERFUSED RAT HEART : Myocardial Metabolism : IV Auditorium : PROCEEDINGS OF THE 44th ANNUAL SCIENTIFIC MEETING OF THE JAPANESE CIRCULATION SOCIETY
- An O(p^3) Algorithm for Finding Hamiltonian Cycles in Certain Digraphs