On the parallel complexity of the alternating Hamiltonian cycle problem

DOI10.1051/RO:1999119MaRDI QIDQ4497876zbMATH OpenOpenAlexFDO

Authors Ioannis Milis, Evripidis Bampis, Y. Manoussakis

Publication date 24 August 2000

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_1999__33_4_421_0/, https://eudml.org/doc/197799

zbMATH Keywords

Hamiltonian cyclegraph with colored edges

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 718675
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

Cited in

(6)

• The parity Hamiltonian cycle problem in directed graphs
• The parity Hamiltonian cycle problem
• On the parallel complexity of the alternating Hamiltonian cycle problem
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP

This page was built for publication: On the parallel complexity of the alternating Hamiltonian cycle problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4497876)