loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
9th International Parallel Processing Symposium
Parallel algorithms for maximum matching in interval graphs
Santa Barbara, CA
April 25-April 28
ISBN: 0-8186-7074-6
M.G. Andrews, AT&T Bell Labs., Naperville, IL, USA
M.J. Atallah, AT&T Bell Labs., Naperville, IL, USA
D.Z. Chen, AT&T Bell Labs., Naperville, IL, USA
D.T. Lee, AT&T Bell Labs., Naperville, IL, USA
Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. We present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs an the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O(log/sup 3/ n) time using O(n/log/sup 2/ n) processors on the EREW PRAM and using O(n) processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O(log n) time using O(n) processors if the input intervals are not given already sorted and using O(n/log n) processors otherwise, on the EREW PRAM. On n-processor hypercubes, our algorithm for this case takes O(log n loglog n) time for unsorted input and O(log n) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. We also present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs.
Index Terms:
parallel algorithms; graph theory; hypercube networks; computational complexity; interval graphs; maximum matching; parallel algorithms; disjoint intervals; maximum cardinality matchings; EREW PRAM; hypercube model; EREW PRAM model; processors; computation time; unsorted input; sorted input; optimal sequential algorithms
Citation:
M.G. Andrews, M.J. Atallah, D.Z. Chen, D.T. Lee, "Parallel algorithms for maximum matching in interval graphs," ipps, pp.84, 9th International Parallel Processing Symposium, 1995
Usage of this product signifies your acceptance of the Terms of Use.