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-12-01T06:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_37.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 N09a801d419e64a3ea5999b4513b70a1c
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 N508b82a6d0ba4704a550c86b330198ef
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N9b7d6bf679154af7be87e574969d1853
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 N22828482edab441c876e8762682abe26
24 Nb6c59760bc1a4a068ec74d8c0624f596
25 schema:publisher N30ba10cd5f544072978ba50a126d8ce1
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-12-01T06:52
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N7d82fed811b9400d96616e77efa4076c
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 N026f171003364251905e14e1b0676f8c schema:familyName Reischuk
36 schema:givenName Rüdiger
37 rdf:type schema:Person
38 N05e239d1e88d48548b3b7d3f94c173b2 rdf:first N026f171003364251905e14e1b0676f8c
39 rdf:rest rdf:nil
40 N09a801d419e64a3ea5999b4513b70a1c rdf:first sg:person.011757371347.43
41 rdf:rest N97ccb688526b4af7a5c40969c80161fe
42 N22828482edab441c876e8762682abe26 schema:name doi
43 schema:value 10.1007/978-3-642-45043-3_31
44 rdf:type schema:PropertyValue
45 N30ba10cd5f544072978ba50a126d8ce1 schema:name Springer Nature
46 rdf:type schema:Organisation
47 N3966f87d91e84e539ed48aeca0fc30f2 rdf:first N4fd239aba83b43f783c163257752f3cf
48 rdf:rest N05e239d1e88d48548b3b7d3f94c173b2
49 N4fd239aba83b43f783c163257752f3cf schema:familyName Jansen
50 schema:givenName Klaus
51 rdf:type schema:Person
52 N508b82a6d0ba4704a550c86b330198ef rdf:first Nf4c2a57eaf43419b97179743efd80345
53 rdf:rest N3966f87d91e84e539ed48aeca0fc30f2
54 N665de08d663242d3b39f4f1aefcc9be4 rdf:first sg:person.07466230107.93
55 rdf:rest rdf:nil
56 N7d82fed811b9400d96616e77efa4076c schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N97ccb688526b4af7a5c40969c80161fe rdf:first sg:person.010747716435.82
59 rdf:rest N665de08d663242d3b39f4f1aefcc9be4
60 N9b7d6bf679154af7be87e574969d1853 schema:isbn 978-3-642-45042-6
61 978-3-642-45043-3
62 schema:name Graph-Theoretic Concepts in Computer Science
63 rdf:type schema:Book
64 Nb6c59760bc1a4a068ec74d8c0624f596 schema:name dimensions_id
65 schema:value pub.1031615994
66 rdf:type schema:PropertyValue
67 Nf4c2a57eaf43419b97179743efd80345 schema:familyName Brandstädt
68 schema:givenName Andreas
69 rdf:type schema:Person
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)


...