|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 9 van 10 gevonden artikelen
| Titel: |
PARALLEL APPROXIMATE MATCHING |
| Auteur: |
Spencer, Thomas H. |
| Verschenen in: |
International journal of parallel, emergent and distributed systems |
| Paginering: | Jaargang 2 (1994) nr. 1-2 pagina's 115-121 |
| Jaar: |
1994 |
| Inhoud: |
Determining the parallel complexity of maximum cardinality matching in bipartite graphs is one of the most famous open problems in parallel algorithm design. The problem is known to be in RNC, but all known fast (polylogarithmic running time) parallel algorithms that find maximum cardinality matchings require the use of random numbers. Moreover, they are based on matrix algebra, so they are inherently inefficient for sparse graphs. Therefore, we are interested in the problem of finding an approximate maximum cardinality matching. The parallel matching algorithm of Goldberg, Plotkin and Vaidya (FOCS 1988) can be modified so that it runs in O(a2log3n) time on an EREW PRAM with n + m processors and finds a matching of size (1 - 1/a)p when given a graph with n vertices, m edges, and a maximum cardinality matching of size p. The resulting algorithm is deterministic. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 9 van 10 gevonden artikelen
| << vorige | volgende >> |