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/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"
      }, 
      {
        "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/bf01758778", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006688031", 
          "https://doi.org/10.1007/bf01758778"
        ], 
        "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/s003730200000", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013242032", 
          "https://doi.org/10.1007/s003730200000"
        ], 
        "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/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"
      }
    ], 
    "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-11-24T20:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_506.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 N0e4d2927cfe64ad1a869e2bef2a49a5b
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 N8386341b40444a00856c653667bb05b0
17 N92d778690ea64d8a9f00dd3d8c885e87
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 N939764f61086479cadd8b4be08230664
37 Nc977fdac7fdc463f972755c7706e9755
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-11-24T20:55
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nd6df39c12a3b43feb6f8381d48a3b56e
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 N0e4d2927cfe64ad1a869e2bef2a49a5b rdf:first sg:person.010063662176.35
48 rdf:rest N151ec566c3c54330a15b3a4c7677b076
49 N151ec566c3c54330a15b3a4c7677b076 rdf:first sg:person.011757371347.43
50 rdf:rest Nc350650e66a742efb5f65fd323c63535
51 N8386341b40444a00856c653667bb05b0 schema:issueNumber 3-4
52 rdf:type schema:PublicationIssue
53 N92d778690ea64d8a9f00dd3d8c885e87 schema:volumeNumber 62
54 rdf:type schema:PublicationVolume
55 N939764f61086479cadd8b4be08230664 schema:name doi
56 schema:value 10.1007/s00453-010-9481-2
57 rdf:type schema:PropertyValue
58 Nc350650e66a742efb5f65fd323c63535 rdf:first sg:person.07466230107.93
59 rdf:rest rdf:nil
60 Nc977fdac7fdc463f972755c7706e9755 schema:name dimensions_id
61 schema:value pub.1008145151
62 rdf:type schema:PropertyValue
63 Nd6df39c12a3b43feb6f8381d48a3b56e schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
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)


...