Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-06

AUTHORS

Xin He

ABSTRACT

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n3/2) sequential time, orO(log4n) parallel time withO(n3) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log3n) time withO(n) processors on a PRAM.

PAGES

545-559

References to SciGraph publications

  • 1987. Parallel 5-colouring of planar graphs in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1986-12. Coloring planar perfect graphs by decomposition in COMBINATORICA
  • 1987. An algorithm for colouring perfect planar graphs in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01840403

    DOI

    http://dx.doi.org/10.1007/bf01840403

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1020471605


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
              "id": "http://www.grid.ac/institutes/grid.273335.3", 
              "name": [
                "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "He", 
            "givenName": "Xin", 
            "id": "sg:person.011352641523.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-18625-5_42", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033481861", 
              "https://doi.org/10.1007/3-540-18625-5_42"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579263", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037842697", 
              "https://doi.org/10.1007/bf02579263"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-18088-5_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009370613", 
              "https://doi.org/10.1007/3-540-18088-5_25"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1990-06", 
        "datePublishedReg": "1990-06-01", 
        "description": "We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n3/2) sequential time, orO(log4n) parallel time withO(n3) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log3n) time withO(n) processors on a PRAM.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01840403", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "5"
          }
        ], 
        "keywords": [
          "sequential implementation", 
          "efficient parallel", 
          "parallel implementation", 
          "sequential algorithm", 
          "efficient algorithm", 
          "planar graphs", 
          "parallel time", 
          "algorithm", 
          "processors", 
          "sequential time", 
          "graph", 
          "implementation", 
          "PRAM", 
          "time", 
          "parallel", 
          "problem", 
          "perfect planar graphs"
        ], 
        "name": "Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs", 
        "pagination": "545-559", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020471605"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01840403"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01840403", 
          "https://app.dimensions.ai/details/publication/pub.1020471605"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_249.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01840403"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01840403'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01840403'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01840403'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01840403'


     

    This table displays all metadata directly associated to this object as RDF triples.

    87 TRIPLES      22 PREDICATES      46 URIs      35 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01840403 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N6870177121c04ae0b629686990d39806
    4 schema:citation sg:pub.10.1007/3-540-18088-5_25
    5 sg:pub.10.1007/3-540-18625-5_42
    6 sg:pub.10.1007/bf02579263
    7 schema:datePublished 1990-06
    8 schema:datePublishedReg 1990-06-01
    9 schema:description We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n3/2) sequential time, orO(log4n) parallel time withO(n3) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log3n) time withO(n) processors on a PRAM.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N11d105f6c84a49afb13d38cdaae804aa
    14 N39d2d943f9f645c19d9ef6b425debf1a
    15 sg:journal.1047644
    16 schema:keywords PRAM
    17 algorithm
    18 efficient algorithm
    19 efficient parallel
    20 graph
    21 implementation
    22 parallel
    23 parallel implementation
    24 parallel time
    25 perfect planar graphs
    26 planar graphs
    27 problem
    28 processors
    29 sequential algorithm
    30 sequential implementation
    31 sequential time
    32 time
    33 schema:name Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
    34 schema:pagination 545-559
    35 schema:productId N7efc796572a04289b9f5b4db28c6bf05
    36 Na56280372fc14083aad7f81be9184562
    37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020471605
    38 https://doi.org/10.1007/bf01840403
    39 schema:sdDatePublished 2021-12-01T19:08
    40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    41 schema:sdPublisher N5df945ea3a954385be4237a6f667f887
    42 schema:url https://doi.org/10.1007/bf01840403
    43 sgo:license sg:explorer/license/
    44 sgo:sdDataset articles
    45 rdf:type schema:ScholarlyArticle
    46 N11d105f6c84a49afb13d38cdaae804aa schema:issueNumber 1-4
    47 rdf:type schema:PublicationIssue
    48 N39d2d943f9f645c19d9ef6b425debf1a schema:volumeNumber 5
    49 rdf:type schema:PublicationVolume
    50 N5df945ea3a954385be4237a6f667f887 schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 N6870177121c04ae0b629686990d39806 rdf:first sg:person.011352641523.42
    53 rdf:rest rdf:nil
    54 N7efc796572a04289b9f5b4db28c6bf05 schema:name dimensions_id
    55 schema:value pub.1020471605
    56 rdf:type schema:PropertyValue
    57 Na56280372fc14083aad7f81be9184562 schema:name doi
    58 schema:value 10.1007/bf01840403
    59 rdf:type schema:PropertyValue
    60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Information and Computing Sciences
    62 rdf:type schema:DefinedTerm
    63 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Computation Theory and Mathematics
    65 rdf:type schema:DefinedTerm
    66 sg:journal.1047644 schema:issn 0178-4617
    67 1432-0541
    68 schema:name Algorithmica
    69 schema:publisher Springer Nature
    70 rdf:type schema:Periodical
    71 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
    72 schema:familyName He
    73 schema:givenName Xin
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
    75 rdf:type schema:Person
    76 sg:pub.10.1007/3-540-18088-5_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009370613
    77 https://doi.org/10.1007/3-540-18088-5_25
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/3-540-18625-5_42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033481861
    80 https://doi.org/10.1007/3-540-18625-5_42
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/bf02579263 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037842697
    83 https://doi.org/10.1007/bf02579263
    84 rdf:type schema:CreativeWork
    85 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
    86 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
    87 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...