New Approximation Algorithms for Minimum Cycle Bases of Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007-01-01

AUTHORS

Telikepalli Kavitha , Kurt Mehlhorn , Dimitrios Michail

ABSTRACT

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. 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. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction.We present two new algorithms to compute an approximate minimum cycle basis. For any integer k ≥ 1, we give (2k − 1)-approximation algorithms with expected running time O(kmn1 + 2/k + mn(1 + 1/k)(ω − 1)) and deterministic running time O( n3 + 2/k ), respectively. Here ω is the best exponent of matrix multiplication. It is presently known that ω < 2.376. Both algorithms are o( mω) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Θ(mω) bound.We also present a 2-approximation algorithm with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(m^{\omega}\sqrt{n\log n})$\end{document} expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane. More... »

PAGES

512-523

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-70918-3_44

DOI

http://dx.doi.org/10.1007/978-3-540-70918-3_44

DIMENSIONS

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


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"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over \\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} 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. Cycle bases of low weight are useful in a number of contexts, e.g.\u00a0the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction.We present two new algorithms to compute an approximate minimum cycle basis. For any integer k\u2009\u2265\u20091, we give (2k\u2009\u2212\u20091)-approximation algorithms with expected running time O(kmn1\u2009+\u20092/k\u2009+\u2009mn(1\u2009+\u20091/k)(\u03c9\u2009\u2212\u20091)) and deterministic running time O( n3\u2009+\u20092/k ), respectively. Here \u03c9 is the best exponent of matrix multiplication. It is presently known that \u03c9\u2009<\u20092.376. Both algorithms are o( m\u03c9) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the \u0398(m\u03c9) bound.We also present a 2-approximation algorithm with \\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}$O(m^{\\omega}\\sqrt{n\\log n})$\\end{document} expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.", 
    "editor": [
      {
        "familyName": "Thomas", 
        "givenName": "Wolfgang", 
        "type": "Person"
      }, 
      {
        "familyName": "Weil", 
        "givenName": "Pascal", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-70918-3_44", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-70917-6", 
        "978-3-540-70918-3"
      ], 
      "name": "STACS 2007", 
      "type": "Book"
    }, 
    "keywords": [
      "minimum cycle basis", 
      "cycle space", 
      "approximation algorithm", 
      "edge-weighted graph G", 
      "new approximation algorithm", 
      "dense graphs", 
      "vector space", 
      "planar graphs", 
      "complete Euclidean graph", 
      "Euclidean graph", 
      "n vertices", 
      "graph G", 
      "electrical network", 
      "matrix multiplication", 
      "cycle basis", 
      "linear time", 
      "graph", 
      "time O", 
      "new algorithm", 
      "algorithm", 
      "best exponent", 
      "incidence vectors", 
      "space", 
      "number of contexts", 
      "problem", 
      "A set", 
      "exponent", 
      "vertices", 
      "surface reconstruction", 
      "structural engineering", 
      "vector", 
      "sum", 
      "extension", 
      "multiplication", 
      "plane", 
      "set", 
      "edge", 
      "network", 
      "basis", 
      "time", 
      "number", 
      "engineering", 
      "first time", 
      "reconstruction", 
      "low weight", 
      "analysis", 
      "drop", 
      "cycle", 
      "weight", 
      "context", 
      "chemistry"
    ], 
    "name": "New Approximation Algorithms for Minimum Cycle Bases of Graphs", 
    "pagination": "512-523", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035485296"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-70918-3_44"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-70918-3_44", 
      "https://app.dimensions.ai/details/publication/pub.1035485296"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_366.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-70918-3_44"
  }
]
 

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-540-70918-3_44'

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-540-70918-3_44'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70918-3_44'

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-540-70918-3_44'


 

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

132 TRIPLES      22 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-70918-3_44 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc70203db6a224670998492ae80716d67
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. 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. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction.We present two new algorithms to compute an approximate minimum cycle basis. For any integer k ≥ 1, we give (2k − 1)-approximation algorithms with expected running time O(kmn1 + 2/k + mn(1 + 1/k)(ω − 1)) and deterministic running time O( n3 + 2/k ), respectively. Here ω is the best exponent of matrix multiplication. It is presently known that ω < 2.376. Both algorithms are o( mω) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Θ(mω) bound.We also present a 2-approximation algorithm with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(m^{\omega}\sqrt{n\log n})$\end{document} expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.
7 schema:editor N3f6ffb0fc98a43538f5b45c6ce86a9f2
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N020c5ab0d38744f381e5f81e7eb4ad44
11 schema:keywords A set
12 Euclidean graph
13 algorithm
14 analysis
15 approximation algorithm
16 basis
17 best exponent
18 chemistry
19 complete Euclidean graph
20 context
21 cycle
22 cycle basis
23 cycle space
24 dense graphs
25 drop
26 edge
27 edge-weighted graph G
28 electrical network
29 engineering
30 exponent
31 extension
32 first time
33 graph
34 graph G
35 incidence vectors
36 linear time
37 low weight
38 matrix multiplication
39 minimum cycle basis
40 multiplication
41 n vertices
42 network
43 new algorithm
44 new approximation algorithm
45 number
46 number of contexts
47 planar graphs
48 plane
49 problem
50 reconstruction
51 set
52 space
53 structural engineering
54 sum
55 surface reconstruction
56 time
57 time O
58 vector
59 vector space
60 vertices
61 weight
62 schema:name New Approximation Algorithms for Minimum Cycle Bases of Graphs
63 schema:pagination 512-523
64 schema:productId N5ee98239736c45ef9fe2dc3cd4236a51
65 N942bfd8ce76e4f72971992fa2a190161
66 schema:publisher N83aef0e16876499a9da5ec8aff1d0b0c
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035485296
68 https://doi.org/10.1007/978-3-540-70918-3_44
69 schema:sdDatePublished 2022-10-01T06:57
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N1178cce9d8df4e89b91bc9d20532cfcf
72 schema:url https://doi.org/10.1007/978-3-540-70918-3_44
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N020c5ab0d38744f381e5f81e7eb4ad44 schema:isbn 978-3-540-70917-6
77 978-3-540-70918-3
78 schema:name STACS 2007
79 rdf:type schema:Book
80 N0da351fef0e74c558745f31b1c4c347c rdf:first sg:person.011757371347.43
81 rdf:rest N3b6679a440944997893ed803cf52f36a
82 N1178cce9d8df4e89b91bc9d20532cfcf schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N16d7e7547e944c72bae19312e9441602 rdf:first N2aa3868ab5244445b135d5e1423f5c40
85 rdf:rest rdf:nil
86 N2aa3868ab5244445b135d5e1423f5c40 schema:familyName Weil
87 schema:givenName Pascal
88 rdf:type schema:Person
89 N3b6679a440944997893ed803cf52f36a rdf:first sg:person.07510643303.39
90 rdf:rest rdf:nil
91 N3f6ffb0fc98a43538f5b45c6ce86a9f2 rdf:first N822f33d2403a4ba38a59b0a19bb1f66c
92 rdf:rest N16d7e7547e944c72bae19312e9441602
93 N5ee98239736c45ef9fe2dc3cd4236a51 schema:name doi
94 schema:value 10.1007/978-3-540-70918-3_44
95 rdf:type schema:PropertyValue
96 N822f33d2403a4ba38a59b0a19bb1f66c schema:familyName Thomas
97 schema:givenName Wolfgang
98 rdf:type schema:Person
99 N83aef0e16876499a9da5ec8aff1d0b0c schema:name Springer Nature
100 rdf:type schema:Organisation
101 N942bfd8ce76e4f72971992fa2a190161 schema:name dimensions_id
102 schema:value pub.1035485296
103 rdf:type schema:PropertyValue
104 Nc70203db6a224670998492ae80716d67 rdf:first sg:person.015551052213.83
105 rdf:rest N0da351fef0e74c558745f31b1c4c347c
106 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
107 schema:name Information and Computing Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
110 schema:name Computation Theory and Mathematics
111 rdf:type schema:DefinedTerm
112 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
113 schema:familyName Mehlhorn
114 schema:givenName Kurt
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
116 rdf:type schema:Person
117 sg:person.015551052213.83 schema:affiliation grid-institutes:grid.34980.36
118 schema:familyName Kavitha
119 schema:givenName Telikepalli
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015551052213.83
121 rdf:type schema:Person
122 sg:person.07510643303.39 schema:affiliation grid-institutes:grid.419528.3
123 schema:familyName Michail
124 schema:givenName Dimitrios
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07510643303.39
126 rdf:type schema:Person
127 grid-institutes:grid.34980.36 schema:alternateName Indian Institute of Science, Bangalore, India
128 schema:name Indian Institute of Science, Bangalore, India
129 rdf:type schema:Organization
130 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
131 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
132 rdf:type schema:Organization
 




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


...