Algorithms to Compute Minimum Cycle Basis in Directed Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-06

AUTHORS

Telikepalli Kavitha, Kurt Mehlhorn

ABSTRACT

We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,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}${\Bbb Q}$\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 weights of the cycles is minimum is called a minimum cycle basis of G. This paper presents an \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^4n)$\end{document} algorithm, which is the first polynomial-time algorithm for computing a minimum cycle basis in G. We then improve it to an \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^4)$\end{document} algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. 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}${\Bbb GF}(2)$\end{document} generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis in an undirected graph cannot be used as black boxes to solve the problem in directed graphs. More... »

PAGES

485-505

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-006-1319-6

DOI

http://dx.doi.org/10.1007/s00224-006-1319-6

DIMENSIONS

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


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": "CSA Department, Indian Institute of Science, Bangalore 560012, India", 
          "id": "http://www.grid.ac/institutes/grid.34980.36", 
          "name": [
            "CSA Department, Indian Institute of Science, Bangalore 560012, 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 fur Informatik, 66123 Saarbrucken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut fur Informatik, 66123 Saarbrucken, 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"
      }
    ], 
    "datePublished": "2007-06", 
    "datePublishedReg": "2007-06-01", 
    "description": "We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,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}${\\Bbb Q}$\\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 weights of the cycles is minimum is called a minimum cycle basis of G. This paper presents an \\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^4n)$\\end{document} algorithm, which is the first polynomial-time  algorithm for computing a minimum cycle basis in G. We then improve it to an \\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^4)$\\end{document} algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied.  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}${\\Bbb GF}(2)$\\end{document} generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis in an undirected graph cannot be used as black boxes to solve the problem in directed graphs.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00224-006-1319-6", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "40"
      }
    ], 
    "keywords": [
      "undirected graph", 
      "minimum cycle basis", 
      "vector space", 
      "sum of weights", 
      "algorithm", 
      "graph", 
      "underlying undirected graph", 
      "black box", 
      "Directed Graphs", 
      "cycle basis", 
      "non-negative weights", 
      "vector", 
      "space", 
      "graph G", 
      "n vertices", 
      "vertices", 
      "cycle space", 
      "set", 
      "box", 
      "basis", 
      "incidence vectors", 
      "arc", 
      "weight", 
      "cycle", 
      "sum", 
      "low weight", 
      "A set", 
      "problem", 
      "paper"
    ], 
    "name": "Algorithms to Compute Minimum Cycle Basis in Directed Graphs", 
    "pagination": "485-505", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007881668"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-006-1319-6"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-006-1319-6", 
      "https://app.dimensions.ai/details/publication/pub.1007881668"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:53", 
    "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_450.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00224-006-1319-6"
  }
]
 

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/s00224-006-1319-6'

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/s00224-006-1319-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-006-1319-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-006-1319-6'


 

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

96 TRIPLES      20 PREDICATES      54 URIs      46 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-006-1319-6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N097e7ee900284f2cacdbc3408d32ab1e
4 schema:datePublished 2007-06
5 schema:datePublishedReg 2007-06-01
6 schema:description We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,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}${\Bbb Q}$\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 weights of the cycles is minimum is called a minimum cycle basis of G. This paper presents an \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^4n)$\end{document} algorithm, which is the first polynomial-time algorithm for computing a minimum cycle basis in G. We then improve it to an \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^4)$\end{document} algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. 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}${\Bbb GF}(2)$\end{document} generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis in an undirected graph cannot be used as black boxes to solve the problem in directed graphs.
7 schema:genre article
8 schema:isAccessibleForFree false
9 schema:isPartOf N6462006627b1479f952c5ceaeafb671d
10 Nfe8262d163d94bfca8fa395bfd5d130e
11 sg:journal.1052098
12 schema:keywords A set
13 Directed Graphs
14 algorithm
15 arc
16 basis
17 black box
18 box
19 cycle
20 cycle basis
21 cycle space
22 graph
23 graph G
24 incidence vectors
25 low weight
26 minimum cycle basis
27 n vertices
28 non-negative weights
29 paper
30 problem
31 set
32 space
33 sum
34 sum of weights
35 underlying undirected graph
36 undirected graph
37 vector
38 vector space
39 vertices
40 weight
41 schema:name Algorithms to Compute Minimum Cycle Basis in Directed Graphs
42 schema:pagination 485-505
43 schema:productId Nb5e2b6fe18f9484eb448c94613d78f25
44 Nd85ef06954d342cfa9b83f87bb77127a
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007881668
46 https://doi.org/10.1007/s00224-006-1319-6
47 schema:sdDatePublished 2022-09-02T15:53
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N7417c36c011843938e154e793d8c682e
50 schema:url https://doi.org/10.1007/s00224-006-1319-6
51 sgo:license sg:explorer/license/
52 sgo:sdDataset articles
53 rdf:type schema:ScholarlyArticle
54 N097e7ee900284f2cacdbc3408d32ab1e rdf:first sg:person.015551052213.83
55 rdf:rest N53606446967e4500b8dda6a9276898e5
56 N53606446967e4500b8dda6a9276898e5 rdf:first sg:person.011757371347.43
57 rdf:rest rdf:nil
58 N6462006627b1479f952c5ceaeafb671d schema:volumeNumber 40
59 rdf:type schema:PublicationVolume
60 N7417c36c011843938e154e793d8c682e schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Nb5e2b6fe18f9484eb448c94613d78f25 schema:name dimensions_id
63 schema:value pub.1007881668
64 rdf:type schema:PropertyValue
65 Nd85ef06954d342cfa9b83f87bb77127a schema:name doi
66 schema:value 10.1007/s00224-006-1319-6
67 rdf:type schema:PropertyValue
68 Nfe8262d163d94bfca8fa395bfd5d130e schema:issueNumber 4
69 rdf:type schema:PublicationIssue
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computation Theory and Mathematics
75 rdf:type schema:DefinedTerm
76 sg:journal.1052098 schema:issn 1432-4350
77 1433-0490
78 schema:name Theory of Computing Systems
79 schema:publisher Springer Nature
80 rdf:type schema:Periodical
81 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
82 schema:familyName Mehlhorn
83 schema:givenName Kurt
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
85 rdf:type schema:Person
86 sg:person.015551052213.83 schema:affiliation grid-institutes:grid.34980.36
87 schema:familyName Kavitha
88 schema:givenName Telikepalli
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015551052213.83
90 rdf:type schema:Person
91 grid-institutes:grid.34980.36 schema:alternateName CSA Department, Indian Institute of Science, Bangalore 560012, India
92 schema:name CSA Department, Indian Institute of Science, Bangalore 560012, India
93 rdf:type schema:Organization
94 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut fur Informatik, 66123 Saarbrucken, Germany
95 schema:name Max-Planck-Institut fur Informatik, 66123 Saarbrucken, Germany
96 rdf:type schema:Organization
 




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


...