Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs

DOI10.1016/0304-3975(88)90120-XzbMath0666.68033MaRDI QIDQ1116690

Marek Karpinski, Elias Dahlhaus

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cycleparallel algorithmperfect matchingmatching completeness

Mathematics Subject Classification ID

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

Related Items

Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, Matching theory -- a sampler: From Dénes König to the present

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of colouring problems on dense graphs
• Matching theory
• Matching is as easy as matrix inversion
• Parallel algorithms for finding Hamilton cycles in random graphs
• Tree-size bounded alternation
• Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
• Advances in graph theory
• Constructing disjoint paths on expander graphs
• A taxonomy of problems with fast parallel algorithms
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
• A fast parallel algorithm for routing in permutation networks
• A universal interconnection pattern for parallel computers
• An O(logn) parallel connectivity algorithm
• Some Theorems on Abstract Graphs