An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-12-08

AUTHORS

Amr Elmasry, Kurt Mehlhorn, Jens M. Schmidt

ABSTRACT

A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair. More... »

PAGES

754-766

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-010-9481-2

DOI

http://dx.doi.org/10.1007/s00453-010-9481-2

DIMENSIONS

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


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": "MPI f\u00fcr Informatik, Campus E1 4, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "MPI f\u00fcr Informatik, Campus E1 4, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Elmasry", 
        "givenName": "Amr", 
        "id": "sg:person.010063662176.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010063662176.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MPI f\u00fcr Informatik, Campus E1 4, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "MPI f\u00fcr Informatik, Campus E1 4, 66123, 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": "Dept. of Computer Science, FU Berlin, Berlin, Germany", 
          "id": "http://www.grid.ac/institutes/grid.14095.39", 
          "name": [
            "Dept. of Computer Science, FU Berlin, Berlin, 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/s003730200000", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013242032", 
          "https://doi.org/10.1007/s003730200000"
        ], 
        "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/3-540-45749-6_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040585292", 
          "https://doi.org/10.1007/3-540-45749-6_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01758778", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006688031", 
          "https://doi.org/10.1007/bf01758778"
        ], 
        "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"
      }, 
      {
        "id": "sg:pub.10.1007/bf01191205", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002665619", 
          "https://doi.org/10.1007/bf01191205"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-03427-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027700694", 
          "https://doi.org/10.1007/978-3-662-03427-9"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-12-08", 
    "datePublishedReg": "2010-12-08", 
    "description": "A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-010-9481-2", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "62"
      }
    ], 
    "keywords": [
      "Hamiltonian graphs", 
      "linear running time", 
      "input graph", 
      "graph", 
      "running time", 
      "vertices", 
      "algorithm", 
      "triconnectivity", 
      "checkable proofs", 
      "separation pair", 
      "proof", 
      "removal", 
      "time", 
      "fact", 
      "pairs"
    ], 
    "name": "An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs", 
    "pagination": "754-766", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008145151"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-010-9481-2"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-010-9481-2", 
      "https://app.dimensions.ai/details/publication/pub.1008145151"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_516.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-010-9481-2"
  }
]
 

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-010-9481-2'

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-010-9481-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-010-9481-2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-010-9481-2'


 

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

117 TRIPLES      21 PREDICATES      46 URIs      31 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-010-9481-2 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N7d2dceffbf8d49f5a1fd226f95ece6fd
4 schema:citation sg:pub.10.1007/3-540-44541-2_8
5 sg:pub.10.1007/3-540-45749-6_25
6 sg:pub.10.1007/978-3-662-03427-9
7 sg:pub.10.1007/bf01191205
8 sg:pub.10.1007/bf01758778
9 sg:pub.10.1007/bf02122557
10 sg:pub.10.1007/s003730200000
11 schema:datePublished 2010-12-08
12 schema:datePublishedReg 2010-12-08
13 schema:description A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair.
14 schema:genre article
15 schema:isAccessibleForFree true
16 schema:isPartOf Nbe19349eedab4a1e9ee1fb1489159b2c
17 Nf15db3a5851c4feb8fe95e093436e5f5
18 sg:journal.1047644
19 schema:keywords Hamiltonian graphs
20 algorithm
21 checkable proofs
22 fact
23 graph
24 input graph
25 linear running time
26 pairs
27 proof
28 removal
29 running time
30 separation pair
31 time
32 triconnectivity
33 vertices
34 schema:name An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs
35 schema:pagination 754-766
36 schema:productId N29f3a29bcfc342d08064268a9da416c5
37 N58de8702ec584f5098ee5f5522d76c66
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008145151
39 https://doi.org/10.1007/s00453-010-9481-2
40 schema:sdDatePublished 2022-09-02T15:54
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nd2b13c26f1254d0c8a9796e7699a40cd
43 schema:url https://doi.org/10.1007/s00453-010-9481-2
44 sgo:license sg:explorer/license/
45 sgo:sdDataset articles
46 rdf:type schema:ScholarlyArticle
47 N29f3a29bcfc342d08064268a9da416c5 schema:name doi
48 schema:value 10.1007/s00453-010-9481-2
49 rdf:type schema:PropertyValue
50 N394506dd94984795997d81196214bcee rdf:first sg:person.07466230107.93
51 rdf:rest rdf:nil
52 N58de8702ec584f5098ee5f5522d76c66 schema:name dimensions_id
53 schema:value pub.1008145151
54 rdf:type schema:PropertyValue
55 N68dda6c25cb54304bd18042a20e5ae7e rdf:first sg:person.011757371347.43
56 rdf:rest N394506dd94984795997d81196214bcee
57 N7d2dceffbf8d49f5a1fd226f95ece6fd rdf:first sg:person.010063662176.35
58 rdf:rest N68dda6c25cb54304bd18042a20e5ae7e
59 Nbe19349eedab4a1e9ee1fb1489159b2c schema:volumeNumber 62
60 rdf:type schema:PublicationVolume
61 Nd2b13c26f1254d0c8a9796e7699a40cd schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 Nf15db3a5851c4feb8fe95e093436e5f5 schema:issueNumber 3-4
64 rdf:type schema:PublicationIssue
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
69 schema:name Computation Theory and Mathematics
70 rdf:type schema:DefinedTerm
71 sg:journal.1047644 schema:issn 0178-4617
72 1432-0541
73 schema:name Algorithmica
74 schema:publisher Springer Nature
75 rdf:type schema:Periodical
76 sg:person.010063662176.35 schema:affiliation grid-institutes:grid.419528.3
77 schema:familyName Elmasry
78 schema:givenName Amr
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010063662176.35
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.14095.39
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 sg:pub.10.1007/3-540-44541-2_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003031596
92 https://doi.org/10.1007/3-540-44541-2_8
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/3-540-45749-6_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040585292
95 https://doi.org/10.1007/3-540-45749-6_25
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/978-3-662-03427-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027700694
98 https://doi.org/10.1007/978-3-662-03427-9
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf01191205 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002665619
101 https://doi.org/10.1007/bf01191205
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/bf01758778 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006688031
104 https://doi.org/10.1007/bf01758778
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bf02122557 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049525355
107 https://doi.org/10.1007/bf02122557
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/s003730200000 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013242032
110 https://doi.org/10.1007/s003730200000
111 rdf:type schema:CreativeWork
112 grid-institutes:grid.14095.39 schema:alternateName Dept. of Computer Science, FU Berlin, Berlin, Germany
113 schema:name Dept. of Computer Science, FU Berlin, Berlin, Germany
114 rdf:type schema:Organization
115 grid-institutes:grid.419528.3 schema:alternateName MPI für Informatik, Campus E1 4, 66123, Saarbrücken, Germany
116 schema:name MPI für Informatik, Campus E1 4, 66123, Saarbrücken, Germany
117 rdf:type schema:Organization
 




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


...