Isolation, matching, and counting

E Allender; K Reinhardt

doi:10.1109/CCC.1998.694594

Back

Conference proceeding

Isolation, matching, and counting

E Allender and K Reinhardt

Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247), pp.92-100

1998

DOI: https://doi.org/10.1109/CCC.1998.694594

Abstract

Computer science

Upper bound

Polynomials

We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.

Metrics

4 Record Views

4 Times Cited - Web of Science

Details

Title: Isolation, matching, and counting
Creators: E Allender - Dept. of Comput. Eng., Rutgers Univ., Piscataway, NJ, USA
K Reinhardt
Publication Details: Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247), pp.92-100
Date published: 1998
Publisher: IEEE
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Conference proceeding
Identifiers: 991031654930104646