On the parallel complexity of the alternating Hamiltonian cycle problem

DOI10.1051/RO:1999119zbMATH Open0952.68115OpenAlexW2112126377MaRDI QIDQ4497876FDOQ4497876

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/

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

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)

Cited In (5)

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

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)