
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 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 AC^{0}hardness of the general matching problem for various degree definable graph classes. General matching belongs to randomized NC^{2} [MVV]. The deterministic parallel status of the general matching problem (NC or NChard 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 NC^{2}. We shall show that the problem of perfect matching restricted to 2connected graphs of maximal degree 3, regular 2connected graphs of degree 4, regular graphs of degree 3, and graphs of minimal degree αG for α < 1/2 are AC^{0}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 