Symmetric Complementation


Journal Article

This paper introduces a new class of games called symmetric complementing games. These games are interesting since their related complexity classes include many well-known graph problems: Finding mlmmum spanning forests; k-connectiwty and k-blocks; and recognition of chordal graphs, comparabdity graphs, interval graphs, spht graphs, permutation graphs, and constant valence planar graphs. For these problems probabihstlc sequential algorithms requiring simultaneously logarithmic space and polynomial time are given Furthermore, probabfllsUc parallelism algorithms requiring simultaneously loganthmic time and a polynomml number of processors are also given. © 1984, ACM. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • March 30, 1984

Published In

Volume / Issue

  • 31 / 2

Start / End Page

  • 401 - 421

Electronic International Standard Serial Number (EISSN)

  • 1557-735X

International Standard Serial Number (ISSN)

  • 0004-5411

Digital Object Identifier (DOI)

  • 10.1145/62.322436

Citation Source

  • Scopus