Minimum Cycle Bases in Graphs Algorithms and Applications View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Kurt Mehlhorn

ABSTRACT

A cycle basis of a graph is a family of cycles which spans all cycles of the graph. In an undirected graph, a cycle is simply a set of edges with respect to which every vertex has even degree. We view cycles as vectors indexed by edges. The entry for an edge is one if the edge belongs to the cycle and is zero otherwise. Addition of cycles corresponds to vector addition modulo 2 (symmetric difference of the underlying edge sets). In this way, the cycles of a graph form a vector space and a cycle basis is simply a basis of this vector space. The notion for directed graphs is slightly more involved. More... »

PAGES

13-14

Book

TITLE

Mathematical Foundations of Computer Science 2007

ISBN

978-3-540-74455-9
978-3-540-74456-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74456-6_3

DOI

http://dx.doi.org/10.1007/978-3-540-74456-6_3

DIMENSIONS

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


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": "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"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "A cycle basis of a graph is a family of cycles which spans all cycles of the graph. In an undirected graph, a cycle is simply a set of edges with respect to which every vertex has even degree. We view cycles as vectors indexed by edges. The entry for an edge is one if the edge belongs to the cycle and is zero otherwise. Addition of cycles corresponds to vector addition modulo 2 (symmetric difference of the underlying edge sets). In this way, the cycles of a graph form a vector space and a cycle basis is simply a basis of this vector space. The notion for directed graphs is slightly more involved.", 
    "editor": [
      {
        "familyName": "Ku\u010dera", 
        "givenName": "Lud\u011bk", 
        "type": "Person"
      }, 
      {
        "familyName": "Ku\u010dera", 
        "givenName": "Anton\u00edn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74456-6_3", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74455-9", 
        "978-3-540-74456-6"
      ], 
      "name": "Mathematical Foundations of Computer Science 2007", 
      "type": "Book"
    }, 
    "keywords": [
      "vector space", 
      "family of cycles", 
      "set of edges", 
      "addition modulo 2", 
      "minimum cycle basis", 
      "undirected graph", 
      "graph algorithms", 
      "cycle basis", 
      "graph", 
      "addition of cycles", 
      "modulo 2", 
      "graph form", 
      "space", 
      "edge", 
      "vertices", 
      "algorithm", 
      "set", 
      "vector", 
      "applications", 
      "basis", 
      "notion", 
      "respect", 
      "form", 
      "way", 
      "degree", 
      "family", 
      "cycle", 
      "addition", 
      "entry"
    ], 
    "name": "Minimum Cycle Bases in Graphs Algorithms and Applications", 
    "pagination": "13-14", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048661789"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74456-6_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74456-6_3", 
      "https://app.dimensions.ai/details/publication/pub.1048661789"
    ], 
    "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_323.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-74456-6_3"
  }
]
 

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-74456-6_3'

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-74456-6_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74456-6_3'

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-74456-6_3'


 

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

93 TRIPLES      22 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74456-6_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N18d9bc3bff13407bb99044f440d2fcd1
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description A cycle basis of a graph is a family of cycles which spans all cycles of the graph. In an undirected graph, a cycle is simply a set of edges with respect to which every vertex has even degree. We view cycles as vectors indexed by edges. The entry for an edge is one if the edge belongs to the cycle and is zero otherwise. Addition of cycles corresponds to vector addition modulo 2 (symmetric difference of the underlying edge sets). In this way, the cycles of a graph form a vector space and a cycle basis is simply a basis of this vector space. The notion for directed graphs is slightly more involved.
7 schema:editor N88bd1d9990a74ed68d31b1a5d2425f22
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N478119c546d741d6a10596030e78993e
11 schema:keywords addition
12 addition modulo 2
13 addition of cycles
14 algorithm
15 applications
16 basis
17 cycle
18 cycle basis
19 degree
20 edge
21 entry
22 family
23 family of cycles
24 form
25 graph
26 graph algorithms
27 graph form
28 minimum cycle basis
29 modulo 2
30 notion
31 respect
32 set
33 set of edges
34 space
35 undirected graph
36 vector
37 vector space
38 vertices
39 way
40 schema:name Minimum Cycle Bases in Graphs Algorithms and Applications
41 schema:pagination 13-14
42 schema:productId N87060567cf84487f9cfb37be982e3288
43 Na6d424d7ccfd43a19fdc1ebe07a5b23a
44 schema:publisher Nf43992998345419aa72256fff5a39fe6
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048661789
46 https://doi.org/10.1007/978-3-540-74456-6_3
47 schema:sdDatePublished 2022-10-01T06:57
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N5248bc772de04a148e79d6be301e6377
50 schema:url https://doi.org/10.1007/978-3-540-74456-6_3
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N18d9bc3bff13407bb99044f440d2fcd1 rdf:first sg:person.011757371347.43
55 rdf:rest rdf:nil
56 N1d09f507c189408f928cfa3d92af1190 schema:familyName Kučera
57 schema:givenName Antonín
58 rdf:type schema:Person
59 N45a72225ad024c00b54ca323fd09e32f rdf:first N1d09f507c189408f928cfa3d92af1190
60 rdf:rest rdf:nil
61 N478119c546d741d6a10596030e78993e schema:isbn 978-3-540-74455-9
62 978-3-540-74456-6
63 schema:name Mathematical Foundations of Computer Science 2007
64 rdf:type schema:Book
65 N5248bc772de04a148e79d6be301e6377 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N6586a4ec11be46d1a4173340e4981758 schema:familyName Kučera
68 schema:givenName Luděk
69 rdf:type schema:Person
70 N87060567cf84487f9cfb37be982e3288 schema:name dimensions_id
71 schema:value pub.1048661789
72 rdf:type schema:PropertyValue
73 N88bd1d9990a74ed68d31b1a5d2425f22 rdf:first N6586a4ec11be46d1a4173340e4981758
74 rdf:rest N45a72225ad024c00b54ca323fd09e32f
75 Na6d424d7ccfd43a19fdc1ebe07a5b23a schema:name doi
76 schema:value 10.1007/978-3-540-74456-6_3
77 rdf:type schema:PropertyValue
78 Nf43992998345419aa72256fff5a39fe6 schema:name Springer Nature
79 rdf:type schema:Organisation
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
87 schema:familyName Mehlhorn
88 schema:givenName Kurt
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
90 rdf:type schema:Person
91 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
92 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
93 rdf:type schema:Organization
 




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


...