Minimum Cycle Bases of Weighted Outerplanar Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Tsung-Hao Liu , Hsueh-I. Lu

ABSTRACT

We give the first known optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(ℂ) for a minimum cycle basis ℂ of G. Each cycle in ℂ can be computed from Z(ℂ) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G. More... »

PAGES

564-572

Book

TITLE

Algorithms and Computation

ISBN

978-3-642-10630-9
978-3-642-10631-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_58

DOI

http://dx.doi.org/10.1007/978-3-642-10631-6_58

DIMENSIONS

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


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": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Tsung-Hao", 
        "id": "sg:person.0620511425.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0620511425.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I.", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We give the first known optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(\u2102) for a minimum cycle basis \u2102 of G. Each cycle in \u2102 can be computed from Z(\u2102) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G.", 
    "editor": [
      {
        "familyName": "Dong", 
        "givenName": "Yingfei", 
        "type": "Person"
      }, 
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-10631-6_58", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-10630-9", 
        "978-3-642-10631-6"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "minimum cycle basis", 
      "outerplanar graphs", 
      "outerplanar graph G", 
      "optimal algorithm", 
      "graph G", 
      "cycle basis", 
      "time algorithm", 
      "graph", 
      "compact representation", 
      "algorithm", 
      "representation", 
      "edge", 
      "basis", 
      "results", 
      "time", 
      "cycle"
    ], 
    "name": "Minimum Cycle Bases of Weighted Outerplanar Graphs", 
    "pagination": "564-572", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047255176"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-10631-6_58"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-10631-6_58", 
      "https://app.dimensions.ai/details/publication/pub.1047255176"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_315.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-10631-6_58"
  }
]
 

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-10631-6_58'

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-10631-6_58'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_58'

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-10631-6_58'


 

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

93 TRIPLES      23 PREDICATES      42 URIs      35 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-10631-6_58 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N548d1683094141328b16b452fb7e711a
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We give the first known optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(ℂ) for a minimum cycle basis ℂ of G. Each cycle in ℂ can be computed from Z(ℂ) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G.
7 schema:editor N27ae1c52dd014cb58fd37622eef3f996
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N98af987c819341ee811a4780c02a267d
12 schema:keywords algorithm
13 basis
14 compact representation
15 cycle
16 cycle basis
17 edge
18 graph
19 graph G
20 minimum cycle basis
21 optimal algorithm
22 outerplanar graph G
23 outerplanar graphs
24 representation
25 results
26 time
27 time algorithm
28 schema:name Minimum Cycle Bases of Weighted Outerplanar Graphs
29 schema:pagination 564-572
30 schema:productId N93756b3ecb0b47a48832e6efdf948697
31 Nec4caaff1c4a4ee49c3de9d1b56d5fca
32 schema:publisher N79eac79540fb4507ad285514bf34ed4a
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047255176
34 https://doi.org/10.1007/978-3-642-10631-6_58
35 schema:sdDatePublished 2022-05-20T07:46
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher Nad143d2c96534d6d861b33da8fc0a82e
38 schema:url https://doi.org/10.1007/978-3-642-10631-6_58
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N27ae1c52dd014cb58fd37622eef3f996 rdf:first N840c081f64db44ada6205da27be13510
43 rdf:rest N29c914ab76af448b89152c7488752a84
44 N29c914ab76af448b89152c7488752a84 rdf:first Na96db4292d0f4c18a03fe0bc94122edf
45 rdf:rest Ndc84cb75229340568a3f1ed27f5cbe49
46 N548d1683094141328b16b452fb7e711a rdf:first sg:person.0620511425.57
47 rdf:rest Naf3d68d3647d4b22af8a7c6174a6f206
48 N79eac79540fb4507ad285514bf34ed4a schema:name Springer Nature
49 rdf:type schema:Organisation
50 N840c081f64db44ada6205da27be13510 schema:familyName Dong
51 schema:givenName Yingfei
52 rdf:type schema:Person
53 N93756b3ecb0b47a48832e6efdf948697 schema:name dimensions_id
54 schema:value pub.1047255176
55 rdf:type schema:PropertyValue
56 N98af987c819341ee811a4780c02a267d schema:isbn 978-3-642-10630-9
57 978-3-642-10631-6
58 schema:name Algorithms and Computation
59 rdf:type schema:Book
60 N9d0c9ccf4c9349afb8335d39a897be7b schema:familyName Ibarra
61 schema:givenName Oscar
62 rdf:type schema:Person
63 Na96db4292d0f4c18a03fe0bc94122edf schema:familyName Du
64 schema:givenName Ding-Zhu
65 rdf:type schema:Person
66 Nad143d2c96534d6d861b33da8fc0a82e schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Naf3d68d3647d4b22af8a7c6174a6f206 rdf:first sg:person.013345515575.46
69 rdf:rest rdf:nil
70 Ndc84cb75229340568a3f1ed27f5cbe49 rdf:first N9d0c9ccf4c9349afb8335d39a897be7b
71 rdf:rest rdf:nil
72 Nec4caaff1c4a4ee49c3de9d1b56d5fca schema:name doi
73 schema:value 10.1007/978-3-642-10631-6_58
74 rdf:type schema:PropertyValue
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
82 schema:familyName Lu
83 schema:givenName Hsueh-I.
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
85 rdf:type schema:Person
86 sg:person.0620511425.57 schema:affiliation grid-institutes:grid.19188.39
87 schema:familyName Liu
88 schema:givenName Tsung-Hao
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0620511425.57
90 rdf:type schema:Person
91 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University
92 schema:name Department of Computer Science and Information Engineering, National Taiwan University
93 rdf:type schema:Organization
 




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


...