Certifying 3-Edge-Connectivity View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-09-22

AUTHORS

Kurt Mehlhorn, Adrian Neumann, Jens M. Schmidt

ABSTRACT

We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph. More... »

PAGES

309-335

References to SciGraph publications

  • 1988-03. Rubber bands, convex embeddings and graph connectivity in COMBINATORICA
  • 2013-06-29. A Framework for the Verification of Certifying Computations in JOURNAL OF AUTOMATED REASONING
  • 2006. The Cluster Editing Problem: Implementations and Experiments in PARAMETERIZED AND EXACT COMPUTATION
  • 2005-05-09. A Simple 3-Edge-Connected Component Algorithm in THEORY OF COMPUTING SYSTEMS
  • 2001. A Linear Time Implementation of SPQR-Trees in GRAPH DRAWING
  • 2014. Verification of Certifying Computations through AutoCorres and Simpl in NASA FORMAL METHODS
  • 1992-06. A linear time algorithm for computing 3-edge-connected components in a multigraph in JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS
  • 1975-12. Nearly optimal binary search trees in ACTA INFORMATICA
  • 2008. Graph Theory in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-015-0075-x

    DOI

    http://dx.doi.org/10.1007/s00453-015-0075-x

    DIMENSIONS

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


    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": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
              "id": "http://www.grid.ac/institutes/grid.419528.3", 
              "name": [
                "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mehlhorn", 
            "givenName": "Kurt", 
            "id": "sg:person.011757371347.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
              "id": "http://www.grid.ac/institutes/grid.419528.3", 
              "name": [
                "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Neumann", 
            "givenName": "Adrian", 
            "id": "sg:person.010747716435.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010747716435.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany", 
              "id": "http://www.grid.ac/institutes/grid.419528.3", 
              "name": [
                "Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schmidt", 
            "givenName": "Jens M.", 
            "id": "sg:person.07466230107.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07466230107.93"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11847250_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035844692", 
              "https://doi.org/10.1007/11847250_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44541-2_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003031596", 
              "https://doi.org/10.1007/3-540-44541-2_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-06200-6_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042087635", 
              "https://doi.org/10.1007/978-3-319-06200-6_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-005-1269-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049868789", 
              "https://doi.org/10.1007/s00224-005-1269-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03167564", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022291530", 
              "https://doi.org/10.1007/bf03167564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10817-013-9289-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012390786", 
              "https://doi.org/10.1007/s10817-013-9289-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-84628-970-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109706182", 
              "https://doi.org/10.1007/978-1-84628-970-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00264563", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008918726", 
              "https://doi.org/10.1007/bf00264563"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02122557", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049525355", 
              "https://doi.org/10.1007/bf02122557"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-09-22", 
        "datePublishedReg": "2015-09-22", 
        "description": "We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-015-0075-x", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "77"
          }
        ], 
        "keywords": [
          "input graph", 
          "linear time", 
          "algorithm", 
          "graph", 
          "cactus representation", 
          "parallel edges", 
          "representation", 
          "vertices", 
          "operation", 
          "construction sequence", 
          "time", 
          "edge", 
          "components", 
          "sequence"
        ], 
        "name": "Certifying 3-Edge-Connectivity", 
        "pagination": "309-335", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1036741055"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-015-0075-x"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-015-0075-x", 
          "https://app.dimensions.ai/details/publication/pub.1036741055"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:41", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_679.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-015-0075-x"
      }
    ]
     

    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/s00453-015-0075-x'

    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/s00453-015-0075-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0075-x'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0075-x'


     

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

    121 TRIPLES      21 PREDICATES      47 URIs      30 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-015-0075-x schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nb32ca71ac99d4e0d97c41154bf58ebee
    4 schema:citation sg:pub.10.1007/11847250_2
    5 sg:pub.10.1007/3-540-44541-2_8
    6 sg:pub.10.1007/978-1-84628-970-5
    7 sg:pub.10.1007/978-3-319-06200-6_4
    8 sg:pub.10.1007/bf00264563
    9 sg:pub.10.1007/bf02122557
    10 sg:pub.10.1007/bf03167564
    11 sg:pub.10.1007/s00224-005-1269-4
    12 sg:pub.10.1007/s10817-013-9289-2
    13 schema:datePublished 2015-09-22
    14 schema:datePublishedReg 2015-09-22
    15 schema:description We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.
    16 schema:genre article
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N08f7ffbcb6b947aba918b1d3bdcb9fdb
    19 Ne60c34e64b9a4a3d86ea55749ce56d93
    20 sg:journal.1047644
    21 schema:keywords algorithm
    22 cactus representation
    23 components
    24 construction sequence
    25 edge
    26 graph
    27 input graph
    28 linear time
    29 operation
    30 parallel edges
    31 representation
    32 sequence
    33 time
    34 vertices
    35 schema:name Certifying 3-Edge-Connectivity
    36 schema:pagination 309-335
    37 schema:productId N64265041c9e244d8bd54a4e1d28446cc
    38 N83eeeffbc4ae4c4aae25fd4e85f96ef2
    39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036741055
    40 https://doi.org/10.1007/s00453-015-0075-x
    41 schema:sdDatePublished 2022-10-01T06:41
    42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    43 schema:sdPublisher N74c508bab16b4ad4b18ad1b344eaa9cd
    44 schema:url https://doi.org/10.1007/s00453-015-0075-x
    45 sgo:license sg:explorer/license/
    46 sgo:sdDataset articles
    47 rdf:type schema:ScholarlyArticle
    48 N08f7ffbcb6b947aba918b1d3bdcb9fdb schema:issueNumber 2
    49 rdf:type schema:PublicationIssue
    50 N0b2a73e82df34162881fc2c82423b42d rdf:first sg:person.07466230107.93
    51 rdf:rest rdf:nil
    52 N41f155da93df47129e39d53ef10fb81f rdf:first sg:person.010747716435.82
    53 rdf:rest N0b2a73e82df34162881fc2c82423b42d
    54 N64265041c9e244d8bd54a4e1d28446cc schema:name dimensions_id
    55 schema:value pub.1036741055
    56 rdf:type schema:PropertyValue
    57 N74c508bab16b4ad4b18ad1b344eaa9cd schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 N83eeeffbc4ae4c4aae25fd4e85f96ef2 schema:name doi
    60 schema:value 10.1007/s00453-015-0075-x
    61 rdf:type schema:PropertyValue
    62 Nb32ca71ac99d4e0d97c41154bf58ebee rdf:first sg:person.011757371347.43
    63 rdf:rest N41f155da93df47129e39d53ef10fb81f
    64 Ne60c34e64b9a4a3d86ea55749ce56d93 schema:volumeNumber 77
    65 rdf:type schema:PublicationVolume
    66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Information and Computing Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Computation Theory and Mathematics
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1047644 schema:issn 0178-4617
    73 1432-0541
    74 schema:name Algorithmica
    75 schema:publisher Springer Nature
    76 rdf:type schema:Periodical
    77 sg:person.010747716435.82 schema:affiliation grid-institutes:grid.419528.3
    78 schema:familyName Neumann
    79 schema:givenName Adrian
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010747716435.82
    81 rdf:type schema:Person
    82 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
    83 schema:familyName Mehlhorn
    84 schema:givenName Kurt
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
    86 rdf:type schema:Person
    87 sg:person.07466230107.93 schema:affiliation grid-institutes:grid.419528.3
    88 schema:familyName Schmidt
    89 schema:givenName Jens M.
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07466230107.93
    91 rdf:type schema:Person
    92 sg:pub.10.1007/11847250_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035844692
    93 https://doi.org/10.1007/11847250_2
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/3-540-44541-2_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003031596
    96 https://doi.org/10.1007/3-540-44541-2_8
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/978-1-84628-970-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109706182
    99 https://doi.org/10.1007/978-1-84628-970-5
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-3-319-06200-6_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042087635
    102 https://doi.org/10.1007/978-3-319-06200-6_4
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/bf00264563 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008918726
    105 https://doi.org/10.1007/bf00264563
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/bf02122557 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049525355
    108 https://doi.org/10.1007/bf02122557
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/bf03167564 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022291530
    111 https://doi.org/10.1007/bf03167564
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/s00224-005-1269-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049868789
    114 https://doi.org/10.1007/s00224-005-1269-4
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/s10817-013-9289-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012390786
    117 https://doi.org/10.1007/s10817-013-9289-2
    118 rdf:type schema:CreativeWork
    119 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Saarbrücken, Germany
    120 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
    121 rdf:type schema:Organization
     




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


    ...