Skip to search boxSkip to navigationSkip to main content

Testing isomorphism of outerplanar graphs in parallel

  • University of Warsaw
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution

Related Event

Title

13th Symposium on Mathematical Foundations of Computer Science, MFCS 1988

Event type

Conference

Date

08/29/1988 - 09/02/1988

Location

CarlsbadSerbia

Abstract

It is shown that isomorphism of two outerplanar graphs with n vertices can be verified on CRCW PRAM in time O(log n) using n processors. This improves the previous results of Ruzzo [R] and Miller & Reif [MR] concerning parallel isomorphism of trees.

Publication Information

Output type

Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution

Original language

English (US)

Pages from-to (Number of pages)

Pages 220-230 (11 pages)

Publication milestones

  • Published - 1988

Publication status

Published - 1988

Publisher

Springer Verlag

Publication series

  • Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print): 0302-9743
    ISSN (Electronic): 1611-3349
    Volume: 324 LNCS

ISBN (Print)

9783540501107

Publication IDs

  • Scopus: 85032868769

Host publication title

Mathematical Foundations of Computer Science 1988 - Proceedings of the 13th Symposium

Host publication editors

  • Michal P. Chytil
  • Vaclav Koubek
  • Ladislav Janiga

Access to documents

Publication metrics

Metrics

Scopus
citations
6, opens in new tab
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1