An Algorithm for Minimum Cycle Basis of Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2007-10-13

AUTHORS

Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch

ABSTRACT

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_{2}$\end{document} generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(mωn), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m2n+mn2log n) algorithm. When the edge weights are integers, we have an O(m2n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(mω) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((mω/ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight. More... »

PAGES

333-349

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-007-9064-z

DOI

http://dx.doi.org/10.1007/s00453-007-9064-z

DIMENSIONS

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


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": "Indian Institute of Science, Bangalore, India", 
          "id": "http://www.grid.ac/institutes/grid.34980.36", 
          "name": [
            "Indian Institute of Science, Bangalore, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kavitha", 
        "givenName": "Telikepalli", 
        "id": "sg:person.015551052213.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015551052213.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, 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-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Michail", 
        "givenName": "Dimitrios", 
        "id": "sg:person.07510643303.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07510643303.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroclaw, Wroclaw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Institute of Computer Science, University of Wroclaw, Wroclaw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paluch", 
        "givenName": "Katarzyna E.", 
        "id": "sg:person.015653672555.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015653672555.22"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/11427186_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028398765", 
          "https://doi.org/10.1007/11427186_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45471-3_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008168021", 
          "https://doi.org/10.1007/3-540-45471-3_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-70918-3_44", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035485296", 
          "https://doi.org/10.1007/978-3-540-70918-3_44"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007-10-13", 
    "datePublishedReg": "2007-10-13", 
    "description": "Abstract\nWe consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_{2}$\\end{document} \ngenerated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g.\u00a0the analysis of electrical networks and structural engineering.\n\nThe previous best algorithm for computing a minimum cycle basis has running time O(m\u03c9n), where \u03c9 is the best exponent of matrix multiplication. It is presently known that \u03c9<2.376. We exhibit an O(m2n+mn2log\u2009n) algorithm. When the edge weights are integers, we have an O(m2n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m\u03c9) time. For any \u03b5>0, we also design an 1+\u03b5 approximation algorithm. The running time of this algorithm is O((m\u03c9/\u03b5)log\u2009(W/\u03b5)) for reasonably dense graphs, where W is the largest edge weight.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-007-9064-z", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "52"
      }
    ], 
    "keywords": [
      "minimum cycle basis", 
      "cycle space", 
      "edge weights", 
      "edge-weighted graph G", 
      "largest edge weight", 
      "dense graphs", 
      "vector space", 
      "approximation algorithm", 
      "unweighted graphs", 
      "n vertices", 
      "previous best algorithm", 
      "graph G", 
      "electrical network", 
      "matrix multiplication", 
      "cycle basis", 
      "running time", 
      "best algorithm", 
      "graph", 
      "algorithm", 
      "best exponent", 
      "incidence vectors", 
      "space", 
      "number of contexts", 
      "problem", 
      "A set", 
      "exponent", 
      "vertices", 
      "structural engineering", 
      "integers", 
      "vector", 
      "sum", 
      "multiplication", 
      "set", 
      "edge", 
      "network", 
      "basis", 
      "time", 
      "number", 
      "engineering", 
      "analysis", 
      "weight", 
      "cycle", 
      "context"
    ], 
    "name": "An Algorithm for Minimum Cycle Basis of Graphs", 
    "pagination": "333-349", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046828573"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-007-9064-z"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-007-9064-z", 
      "https://app.dimensions.ai/details/publication/pub.1046828573"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:51", 
    "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_433.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-007-9064-z"
  }
]
 

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-007-9064-z'

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-007-9064-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9064-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9064-z'


 

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

139 TRIPLES      21 PREDICATES      70 URIs      59 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-007-9064-z schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf9e9e00da8d3495c8096e776c78ac180
4 schema:citation sg:pub.10.1007/11427186_5
5 sg:pub.10.1007/3-540-45471-3_21
6 sg:pub.10.1007/978-3-540-70918-3_44
7 schema:datePublished 2007-10-13
8 schema:datePublishedReg 2007-10-13
9 schema:description Abstract We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_{2}$\end{document} generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(mωn), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m2n+mn2log n) algorithm. When the edge weights are integers, we have an O(m2n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(mω) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((mω/ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight.
10 schema:genre article
11 schema:isAccessibleForFree true
12 schema:isPartOf N8238628629dc4c4180ae93c07455ba3a
13 Nd23ae97001394b309aa70ab52b84182f
14 sg:journal.1047644
15 schema:keywords A set
16 algorithm
17 analysis
18 approximation algorithm
19 basis
20 best algorithm
21 best exponent
22 context
23 cycle
24 cycle basis
25 cycle space
26 dense graphs
27 edge
28 edge weights
29 edge-weighted graph G
30 electrical network
31 engineering
32 exponent
33 graph
34 graph G
35 incidence vectors
36 integers
37 largest edge weight
38 matrix multiplication
39 minimum cycle basis
40 multiplication
41 n vertices
42 network
43 number
44 number of contexts
45 previous best algorithm
46 problem
47 running time
48 set
49 space
50 structural engineering
51 sum
52 time
53 unweighted graphs
54 vector
55 vector space
56 vertices
57 weight
58 schema:name An Algorithm for Minimum Cycle Basis of Graphs
59 schema:pagination 333-349
60 schema:productId N86b90c53b3244088814019aaca71c097
61 Nd54af655c86c432fa80456a00bae49f2
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046828573
63 https://doi.org/10.1007/s00453-007-9064-z
64 schema:sdDatePublished 2022-09-02T15:51
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher N1d9f4a0e52454cd7b9472fb1c3289451
67 schema:url https://doi.org/10.1007/s00453-007-9064-z
68 sgo:license sg:explorer/license/
69 sgo:sdDataset articles
70 rdf:type schema:ScholarlyArticle
71 N1d9f4a0e52454cd7b9472fb1c3289451 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N76dfc612987747e2b2d8d00c6e6535ae rdf:first sg:person.011757371347.43
74 rdf:rest Ne43d23a98c7a415da6d702cd97f76038
75 N8238628629dc4c4180ae93c07455ba3a schema:issueNumber 3
76 rdf:type schema:PublicationIssue
77 N86b90c53b3244088814019aaca71c097 schema:name dimensions_id
78 schema:value pub.1046828573
79 rdf:type schema:PropertyValue
80 Nd23ae97001394b309aa70ab52b84182f schema:volumeNumber 52
81 rdf:type schema:PublicationVolume
82 Nd44d219a3c934792a06e1cf9c2d101ac rdf:first sg:person.015653672555.22
83 rdf:rest rdf:nil
84 Nd54af655c86c432fa80456a00bae49f2 schema:name doi
85 schema:value 10.1007/s00453-007-9064-z
86 rdf:type schema:PropertyValue
87 Ne43d23a98c7a415da6d702cd97f76038 rdf:first sg:person.07510643303.39
88 rdf:rest Nd44d219a3c934792a06e1cf9c2d101ac
89 Nf9e9e00da8d3495c8096e776c78ac180 rdf:first sg:person.015551052213.83
90 rdf:rest N76dfc612987747e2b2d8d00c6e6535ae
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:journal.1047644 schema:issn 0178-4617
98 1432-0541
99 schema:name Algorithmica
100 schema:publisher Springer Nature
101 rdf:type schema:Periodical
102 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
103 schema:familyName Mehlhorn
104 schema:givenName Kurt
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
106 rdf:type schema:Person
107 sg:person.015551052213.83 schema:affiliation grid-institutes:grid.34980.36
108 schema:familyName Kavitha
109 schema:givenName Telikepalli
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015551052213.83
111 rdf:type schema:Person
112 sg:person.015653672555.22 schema:affiliation grid-institutes:grid.8505.8
113 schema:familyName Paluch
114 schema:givenName Katarzyna E.
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015653672555.22
116 rdf:type schema:Person
117 sg:person.07510643303.39 schema:affiliation grid-institutes:grid.419528.3
118 schema:familyName Michail
119 schema:givenName Dimitrios
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07510643303.39
121 rdf:type schema:Person
122 sg:pub.10.1007/11427186_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028398765
123 https://doi.org/10.1007/11427186_5
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/3-540-45471-3_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008168021
126 https://doi.org/10.1007/3-540-45471-3_21
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/978-3-540-70918-3_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035485296
129 https://doi.org/10.1007/978-3-540-70918-3_44
130 rdf:type schema:CreativeWork
131 grid-institutes:grid.34980.36 schema:alternateName Indian Institute of Science, Bangalore, India
132 schema:name Indian Institute of Science, Bangalore, India
133 rdf:type schema:Organization
134 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
135 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
136 rdf:type schema:Organization
137 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wroclaw, Wroclaw, Poland
138 schema:name Institute of Computer Science, University of Wroclaw, Wroclaw, Poland
139 rdf:type schema:Organization
 




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


...