Breaking the O(m2n) Barrier for Minimum Cycle Bases View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Edoardo Amaldi , Claudio Iuliano , Tomasz Jurkiewicz , Kurt Mehlhorn , Romeo Rizzi

ABSTRACT

We give improved algorithms for constructing minimum directed and undirected cycle bases in graphs. For general graphs, the new algorithms are Monte Carlo and have running time O(mω), where ω is the exponent of matrix multiplication. The previous best algorithm had running time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\tilde{O}}(m^2n)$\end{document}. For planar graphs, the new algorithm is deterministic and has running time O(n2). The previous best algorithm had running time O(n2 logn). A key ingredient to our improved running times is the insight that the search for minimum bases can be restricted to a set of candidate cycles of total length O(nm). More... »

PAGES

301-312

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-04128-0_28

DOI

http://dx.doi.org/10.1007/978-3-642-04128-0_28

DIMENSIONS

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


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": "Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy", 
          "id": "http://www.grid.ac/institutes/grid.4643.5", 
          "name": [
            "Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Amaldi", 
        "givenName": "Edoardo", 
        "id": "sg:person.013510766451.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013510766451.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy", 
          "id": "http://www.grid.ac/institutes/grid.4643.5", 
          "name": [
            "Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Iuliano", 
        "givenName": "Claudio", 
        "id": "sg:person.010115573230.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010115573230.05"
        ], 
        "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": "Jurkiewicz", 
        "givenName": "Tomasz", 
        "id": "sg:person.07756502341.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07756502341.63"
        ], 
        "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": "Dipartimento di Matematica ed Informatica, Universit\u00e1 degli Studi di Udine, Udine, Italy", 
          "id": "http://www.grid.ac/institutes/grid.5390.f", 
          "name": [
            "Dipartimento di Matematica ed Informatica, Universit\u00e1 degli Studi di Udine, Udine, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rizzi", 
        "givenName": "Romeo", 
        "id": "sg:person.012014154343.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012014154343.00"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We give improved algorithms for constructing minimum directed and undirected cycle bases in graphs. For general graphs, the new algorithms are Monte Carlo and have running time O(m\u03c9), where \u03c9 is the exponent of matrix multiplication. The previous best algorithm had running time \\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}${\\tilde{O}}(m^2n)$\\end{document}. For planar graphs, the new algorithm is deterministic and has running time O(n2). The previous best algorithm had running time O(n2 logn). A key ingredient to our improved running times is the insight that the search for minimum bases can be restricted to a set of candidate cycles of total length O(nm).", 
    "editor": [
      {
        "familyName": "Fiat", 
        "givenName": "Amos", 
        "type": "Person"
      }, 
      {
        "familyName": "Sanders", 
        "givenName": "Peter", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-04128-0_28", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-04127-3", 
        "978-3-642-04128-0"
      ], 
      "name": "Algorithms - ESA 2009", 
      "type": "Book"
    }, 
    "keywords": [
      "previous best algorithm", 
      "best algorithm", 
      "running time", 
      "new algorithm", 
      "matrix multiplication", 
      "improved algorithm", 
      "general graphs", 
      "algorithm", 
      "graph", 
      "planar graphs", 
      "candidate cycles", 
      "minimum cycle basis", 
      "Monte Carlo", 
      "key ingredient", 
      "cycle basis", 
      "set", 
      "search", 
      "Carlo", 
      "multiplication", 
      "time", 
      "minimum basis", 
      "exponent", 
      "basis", 
      "insights", 
      "length", 
      "ingredients", 
      "total length", 
      "cycle", 
      "barriers"
    ], 
    "name": "Breaking the O(m2n) Barrier for Minimum Cycle Bases", 
    "pagination": "301-312", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006711290"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-04128-0_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-04128-0_28", 
      "https://app.dimensions.ai/details/publication/pub.1006711290"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:15", 
    "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/chapter/chapter_383.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-04128-0_28"
  }
]
 

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-04128-0_28'

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-04128-0_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-04128-0_28'

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-04128-0_28'


 

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

127 TRIPLES      22 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-04128-0_28 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3d6109b1e46e442781cfd73a482ac228
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We give improved algorithms for constructing minimum directed and undirected cycle bases in graphs. For general graphs, the new algorithms are Monte Carlo and have running time O(mω), where ω is the exponent of matrix multiplication. The previous best algorithm had running time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\tilde{O}}(m^2n)$\end{document}. For planar graphs, the new algorithm is deterministic and has running time O(n2). The previous best algorithm had running time O(n2 logn). A key ingredient to our improved running times is the insight that the search for minimum bases can be restricted to a set of candidate cycles of total length O(nm).
7 schema:editor N3a1e2179e94f455093ce5be41f1944ac
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nc7326decbe014c84bd4481e6eed45429
11 schema:keywords Carlo
12 Monte Carlo
13 algorithm
14 barriers
15 basis
16 best algorithm
17 candidate cycles
18 cycle
19 cycle basis
20 exponent
21 general graphs
22 graph
23 improved algorithm
24 ingredients
25 insights
26 key ingredient
27 length
28 matrix multiplication
29 minimum basis
30 minimum cycle basis
31 multiplication
32 new algorithm
33 planar graphs
34 previous best algorithm
35 running time
36 search
37 set
38 time
39 total length
40 schema:name Breaking the O(m2n) Barrier for Minimum Cycle Bases
41 schema:pagination 301-312
42 schema:productId N34e4060ab8c449da874081ebd3ec574e
43 N78a4956e26b44d38a305ad9ce2126533
44 schema:publisher N9596428ad4304f2b9fa17aa4b447a512
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006711290
46 https://doi.org/10.1007/978-3-642-04128-0_28
47 schema:sdDatePublished 2022-09-02T16:15
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N42d1626f55984dcb9709ace6549d7b6e
50 schema:url https://doi.org/10.1007/978-3-642-04128-0_28
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N17470b3f8569450f8af63fc86b987a69 rdf:first sg:person.010115573230.05
55 rdf:rest Nd862ea10d9324deca6ada75490cc7f0e
56 N34e4060ab8c449da874081ebd3ec574e schema:name dimensions_id
57 schema:value pub.1006711290
58 rdf:type schema:PropertyValue
59 N3a1e2179e94f455093ce5be41f1944ac rdf:first N6b1fd5d721f74b7eb0e6bb69476af4d3
60 rdf:rest Nd3ee3fd5123748368247c6ec08c136fd
61 N3d6109b1e46e442781cfd73a482ac228 rdf:first sg:person.013510766451.37
62 rdf:rest N17470b3f8569450f8af63fc86b987a69
63 N42d1626f55984dcb9709ace6549d7b6e schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N6b1fd5d721f74b7eb0e6bb69476af4d3 schema:familyName Fiat
66 schema:givenName Amos
67 rdf:type schema:Person
68 N78a4956e26b44d38a305ad9ce2126533 schema:name doi
69 schema:value 10.1007/978-3-642-04128-0_28
70 rdf:type schema:PropertyValue
71 N9596428ad4304f2b9fa17aa4b447a512 schema:name Springer Nature
72 rdf:type schema:Organisation
73 N9eb7e7e1c4cd41ecb0b045b8a78a199b rdf:first sg:person.012014154343.00
74 rdf:rest rdf:nil
75 Nc5ac5c7b834742a38d458644dfa3ed5d rdf:first sg:person.011757371347.43
76 rdf:rest N9eb7e7e1c4cd41ecb0b045b8a78a199b
77 Nc7326decbe014c84bd4481e6eed45429 schema:isbn 978-3-642-04127-3
78 978-3-642-04128-0
79 schema:name Algorithms - ESA 2009
80 rdf:type schema:Book
81 Nd1335e068d6d46d2b5f9e8b59a745fb7 schema:familyName Sanders
82 schema:givenName Peter
83 rdf:type schema:Person
84 Nd3ee3fd5123748368247c6ec08c136fd rdf:first Nd1335e068d6d46d2b5f9e8b59a745fb7
85 rdf:rest rdf:nil
86 Nd862ea10d9324deca6ada75490cc7f0e rdf:first sg:person.07756502341.63
87 rdf:rest Nc5ac5c7b834742a38d458644dfa3ed5d
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 sg:person.010115573230.05 schema:affiliation grid-institutes:grid.4643.5
95 schema:familyName Iuliano
96 schema:givenName Claudio
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010115573230.05
98 rdf:type schema:Person
99 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
100 schema:familyName Mehlhorn
101 schema:givenName Kurt
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
103 rdf:type schema:Person
104 sg:person.012014154343.00 schema:affiliation grid-institutes:grid.5390.f
105 schema:familyName Rizzi
106 schema:givenName Romeo
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012014154343.00
108 rdf:type schema:Person
109 sg:person.013510766451.37 schema:affiliation grid-institutes:grid.4643.5
110 schema:familyName Amaldi
111 schema:givenName Edoardo
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013510766451.37
113 rdf:type schema:Person
114 sg:person.07756502341.63 schema:affiliation grid-institutes:grid.419528.3
115 schema:familyName Jurkiewicz
116 schema:givenName Tomasz
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07756502341.63
118 rdf:type schema:Person
119 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
120 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
121 rdf:type schema:Organization
122 grid-institutes:grid.4643.5 schema:alternateName Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy
123 schema:name Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy
124 rdf:type schema:Organization
125 grid-institutes:grid.5390.f schema:alternateName Dipartimento di Matematica ed Informatica, Universitá degli Studi di Udine, Udine, Italy
126 schema:name Dipartimento di Matematica ed Informatica, Universitá degli Studi di Udine, Udine, Italy
127 rdf:type schema:Organization
 




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


...