No Access

PARALLEL MAXIMUM MATCHING ALGORITHMS IN INTERVAL GRAPHS

YOOJIN CHUNG

Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea

Search for more papers by this author

KUNSOO PARK

Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea

Search for more papers by this author

, and

YOOKIN CHO

Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea

Search for more papers by this author

https://doi.org/10.1142/S0129054199000058Cited by:3 (Source: Crossref)

Abstract

We develop efficient parallel maximum matching algorithms in interval graphs by exploiting special properties of interval graphs. For general interval graphs, our algorithm requires O(log²v+(n log n/v) time and O(nv²+n²) operations on the CREW PRAM, where n is the number of intervals and v≤n is a parameter. By choosing , we obtain an -time algorithm in O(n²) operations. For v=n/log n, we have an O(log²n)-time algorithm in O(n³/log²n) operations. The best previously known solution takes O(log²n) time using O(n³log²n) operations. For proper interval graphs, our algorithm runs in O(log n) time using O(n) operations if input intervals are sorted and using O(nlog n) operations otherwise on the EREW PRAM.