Publication Details
Title: A Parallel Algorithm for Maximum Matching in Planar Graphs
Author: M. Karpinski, E. Dahlhaus, and A. Lingas
Group: ICSI Technical Reports
Date: April 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-18.pdf
Overview:
We present a new parallel algorithm for finding a maximum (cardinality) matching in a planar bipartite graph G. Our algorithm is processor-time product efficient if the size l of a maximum matching of G is large. It runs in time O((n/2-l + (the square root of n))log (superscript 7)n) on a CRCW PRAM with O(n(superscript 1.5)log (superscript 3)n) processors.
Bibliographic Information:
ICSI Technical Report TR-89-018
Bibliographic Reference:
M. Karpinski, E. Dahlhaus, and A. Lingas. A Parallel Algorithm for Maximum Matching in Planar Graphs. ICSI Technical Report TR-89-018, April 1989
Author: M. Karpinski, E. Dahlhaus, and A. Lingas
Group: ICSI Technical Reports
Date: April 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-18.pdf
Overview:
We present a new parallel algorithm for finding a maximum (cardinality) matching in a planar bipartite graph G. Our algorithm is processor-time product efficient if the size l of a maximum matching of G is large. It runs in time O((n/2-l + (the square root of n))log (superscript 7)n) on a CRCW PRAM with O(n(superscript 1.5)log (superscript 3)n) processors.
Bibliographic Information:
ICSI Technical Report TR-89-018
Bibliographic Reference:
M. Karpinski, E. Dahlhaus, and A. Lingas. A Parallel Algorithm for Maximum Matching in Planar Graphs. ICSI Technical Report TR-89-018, April 1989