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-12-01T06:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_323.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 Nc8aed8270d3449a3a9c4b43c22524e90
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 N9be03ca953a344e09436ce2ef45672d3
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N3d9bcca9706e4cf7bcc4576e67c868ab
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 N15e9cc702a614ad89d7b899d0ac21377
65 Nb8142a0f755147b18d6c966939a3d3fc
66 schema:publisher Ned5c6c0d6139489b93639c7fc9d5f245
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-12-01T06:51
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher Ned766042d44241439f49b94d11c1f50e
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 N15e9cc702a614ad89d7b899d0ac21377 schema:name dimensions_id
77 schema:value pub.1035485296
78 rdf:type schema:PropertyValue
79 N34b15cea914b454eb31a986e55237bd9 schema:familyName Weil
80 schema:givenName Pascal
81 rdf:type schema:Person
82 N3d9bcca9706e4cf7bcc4576e67c868ab schema:isbn 978-3-540-70917-6
83 978-3-540-70918-3
84 schema:name STACS 2007
85 rdf:type schema:Book
86 N3eeb93e5b3b0412d9b5ffdc84fd47ee7 rdf:first sg:person.011757371347.43
87 rdf:rest N6fd43b07bb08409bb71b6e52f14f7528
88 N6fd43b07bb08409bb71b6e52f14f7528 rdf:first sg:person.07510643303.39
89 rdf:rest rdf:nil
90 N991ccb4522d44e7595c0a6888bf2ead0 rdf:first N34b15cea914b454eb31a986e55237bd9
91 rdf:rest rdf:nil
92 N9be03ca953a344e09436ce2ef45672d3 rdf:first Na52c12c666594f64b003096d7db7337e
93 rdf:rest N991ccb4522d44e7595c0a6888bf2ead0
94 Na52c12c666594f64b003096d7db7337e schema:familyName Thomas
95 schema:givenName Wolfgang
96 rdf:type schema:Person
97 Nb8142a0f755147b18d6c966939a3d3fc schema:name doi
98 schema:value 10.1007/978-3-540-70918-3_44
99 rdf:type schema:PropertyValue
100 Nc8aed8270d3449a3a9c4b43c22524e90 rdf:first sg:person.015551052213.83
101 rdf:rest N3eeb93e5b3b0412d9b5ffdc84fd47ee7
102 Ned5c6c0d6139489b93639c7fc9d5f245 schema:name Springer Nature
103 rdf:type schema:Organisation
104 Ned766042d44241439f49b94d11c1f50e schema:name Springer Nature - SN SciGraph project
105 rdf:type schema:Organization
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)


...