Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V
859

27.11.2008

Parallel Complexity for Matching Restricted to Degree Defined Graph Classes
Elias Dahlhaus and Marek Karpinski
[Download PostScript] [Download PDF]

This paper develops on one hand deterministic parallel algorithms (deterministic NC) and proves on the other hand AC0-hardness of the general matching problem for various degree definable graph classes. General matching belongs to randomized NC2 [MVV]. The deterministic parallel status of the general matching problem (NC or NC-hard for P or nothing of both) is unknown. We will prove that the construction of a perfect matching for graphs of an even number of vertices and a minimal degree of |G|/2 can be done in NC2. We shall show that the problem of perfect matching restricted to 2-connected graphs of maximal degree 3, regular 2-connected graphs of degree 4, regular graphs of degree 3, and graphs of minimal degree α|G| for α < 1/2 are AC0-hard for the general matching problem.

Last Change: 11/27/08 at 12:31:16
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V