• DocumentCode
    1988812
  • Title

    An efficient parallel recognition algorithm of parity graphs

  • Author

    Dahlhaus, Elias

  • Author_Institution
    Basser Dept. of Comput. Sci., Sydney Univ., NSW, Australia
  • fYear
    1993
  • fDate
    27-29 May 1993
  • Firstpage
    82
  • Lastpage
    86
  • Abstract
    A parallel algorithm is developed which recognizes parity graphs in O(log2 n) time using a linear number of processors. This improves previous results of G. Adhar and S. Peng (J. Algorithms, vol. 11, pp. 252-284, 1990) and of T. Przytycka and D. Corneil (J. Algorithms, vol. 12, pp. 96-109, 1991)
  • Keywords
    computational complexity; graph theory; parallel algorithms; parity; pattern recognition; computation theory; linear processor number; parallel algorithm; parity graph recognition algorithm; Bipartite graph; Computer science; Concurrent computing; Databases; Gaussian processes; Operations research; Parallel algorithms; Parallel processing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
  • Conference_Location
    Sudbury, Ont.
  • Print_ISBN
    0-8186-4212-2
  • Type

    conf

  • DOI
    10.1109/ICCI.1993.315399
  • Filename
    315399
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1988812