Certifying 3-Edge-Connectivity View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Kurt Mehlhorn , Adrian Neumann , Jens M. Schmidt

ABSTRACT

We present a linear-time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. More... »

PAGES

358-369

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-642-45042-6
978-3-642-45043-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-45043-3_31

DOI

http://dx.doi.org/10.1007/978-3-642-45043-3_31

DIMENSIONS

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


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"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We present a linear-time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity.", 
    "editor": [
      {
        "familyName": "Brandst\u00e4dt", 
        "givenName": "Andreas", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Reischuk", 
        "givenName": "R\u00fcdiger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-45043-3_31", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-45042-6", 
        "978-3-642-45043-3"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "input graph G", 
      "algorithm", 
      "parallel edges", 
      "graph", 
      "nodes", 
      "graph G", 
      "operation", 
      "construction sequence", 
      "edge", 
      "sequence"
    ], 
    "name": "Certifying 3-Edge-Connectivity", 
    "pagination": "358-369", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031615994"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-45043-3_31"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-45043-3_31", 
      "https://app.dimensions.ai/details/publication/pub.1031615994"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:54", 
    "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/chapter/chapter_236.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-45043-3_31"
  }
]
 

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/978-3-642-45043-3_31'

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/978-3-642-45043-3_31'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45043-3_31'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45043-3_31'


 

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

93 TRIPLES      22 PREDICATES      35 URIs      28 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-45043-3_31 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N98686bc3f67041ac941ad6af3b9c947e
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We present a linear-time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity.
7 schema:editor N79adcb1803f348a98315986cdb981243
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N0b73990ca6da4d718dc0bbc635605793
11 schema:keywords algorithm
12 construction sequence
13 edge
14 graph
15 graph G
16 input graph G
17 nodes
18 operation
19 parallel edges
20 sequence
21 schema:name Certifying 3-Edge-Connectivity
22 schema:pagination 358-369
23 schema:productId N44668b0bd6b043309faf0c059b6fe2b7
24 N8bf1a57c3b5e43e4b770edfb4d5ebb34
25 schema:publisher Ndbba9fd195714c66bc27b3df04ebdd08
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031615994
27 https://doi.org/10.1007/978-3-642-45043-3_31
28 schema:sdDatePublished 2022-10-01T06:54
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N34a898b6967e49e0b0a9fa9cbab7b82a
31 schema:url https://doi.org/10.1007/978-3-642-45043-3_31
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N0b73990ca6da4d718dc0bbc635605793 schema:isbn 978-3-642-45042-6
36 978-3-642-45043-3
37 schema:name Graph-Theoretic Concepts in Computer Science
38 rdf:type schema:Book
39 N34a898b6967e49e0b0a9fa9cbab7b82a schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N44668b0bd6b043309faf0c059b6fe2b7 schema:name dimensions_id
42 schema:value pub.1031615994
43 rdf:type schema:PropertyValue
44 N79adcb1803f348a98315986cdb981243 rdf:first N82b1755c9f9646fbb8d0707355d9bf3b
45 rdf:rest Nb457f9cdb216466d8e6b189cca6f794a
46 N80dbcb0b80e4427e96e19e27e05f356e rdf:first sg:person.07466230107.93
47 rdf:rest rdf:nil
48 N82b1755c9f9646fbb8d0707355d9bf3b schema:familyName Brandstädt
49 schema:givenName Andreas
50 rdf:type schema:Person
51 N8bf1a57c3b5e43e4b770edfb4d5ebb34 schema:name doi
52 schema:value 10.1007/978-3-642-45043-3_31
53 rdf:type schema:PropertyValue
54 N9689d0f1b3fa41a59e99f707533032a0 schema:familyName Reischuk
55 schema:givenName Rüdiger
56 rdf:type schema:Person
57 N98686bc3f67041ac941ad6af3b9c947e rdf:first sg:person.011757371347.43
58 rdf:rest Nc14602aea6b8467ea60a4c0bd1e01924
59 Na35139ade3b044cab4dfd188ee1c4349 schema:familyName Jansen
60 schema:givenName Klaus
61 rdf:type schema:Person
62 Nb457f9cdb216466d8e6b189cca6f794a rdf:first Na35139ade3b044cab4dfd188ee1c4349
63 rdf:rest Nd94c563ae90148d0b3aa1d9644332326
64 Nc14602aea6b8467ea60a4c0bd1e01924 rdf:first sg:person.010747716435.82
65 rdf:rest N80dbcb0b80e4427e96e19e27e05f356e
66 Nd94c563ae90148d0b3aa1d9644332326 rdf:first N9689d0f1b3fa41a59e99f707533032a0
67 rdf:rest rdf:nil
68 Ndbba9fd195714c66bc27b3df04ebdd08 schema:name Springer Nature
69 rdf:type schema:Organisation
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computation Theory and Mathematics
75 rdf:type schema:DefinedTerm
76 sg:person.010747716435.82 schema:affiliation grid-institutes:grid.419528.3
77 schema:familyName Neumann
78 schema:givenName Adrian
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010747716435.82
80 rdf:type schema:Person
81 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
82 schema:familyName Mehlhorn
83 schema:givenName Kurt
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
85 rdf:type schema:Person
86 sg:person.07466230107.93 schema:affiliation grid-institutes:grid.419528.3
87 schema:familyName Schmidt
88 schema:givenName Jens M.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07466230107.93
90 rdf:type schema:Person
91 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Saarbrücken, Germany
92 schema:name Max Planck Institute for Informatics, Saarbrücken, Germany
93 rdf:type schema:Organization
 




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


...