Symbolic Coloured SCC Decomposition View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2021-03-23

AUTHORS

Nikola Beneš , Luboš Brim , Samuel Pastva , David Šafránek

ABSTRACT

Problems arising in many scientific disciplines are often modelled using edge-coloured directed graphs. These can be enormous in the number of both vertices and colours. Given such a graph, the original problem frequently translates to the detection of the graph’s strongly connected components, which is challenging at this scale.We propose a new, symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs O(p·n·logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(p\cdot n\cdot \log n)$$\end{document} symbolic steps, where p is the number of colours and n the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to 248\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{48}$$\end{document}) coloured graphs produced by models appearing in systems biology. More... »

PAGES

64-83

Book

TITLE

Tools and Algorithms for the Construction and Analysis of Systems

ISBN

978-3-030-72012-4
978-3-030-72013-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-72013-1_4

DOI

http://dx.doi.org/10.1007/978-3-030-72013-1_4

DIMENSIONS

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


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": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bene\u0161", 
        "givenName": "Nikola", 
        "id": "sg:person.014465763501.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014465763501.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brim", 
        "givenName": "Lubo\u0161", 
        "id": "sg:person.0645117057.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pastva", 
        "givenName": "Samuel", 
        "id": "sg:person.016130263073.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016130263073.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "\u0160afr\u00e1nek", 
        "givenName": "David", 
        "id": "sg:person.011410250615.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011410250615.43"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2021-03-23", 
    "datePublishedReg": "2021-03-23", 
    "description": "Problems arising in many scientific disciplines are often modelled using edge-coloured directed graphs. These can be enormous in the number of both vertices and colours. Given such a graph, the original problem frequently translates to the detection of the graph\u2019s strongly connected components, which is challenging at this scale.We propose a new, symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs O(p\u00b7n\u00b7logn)\\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(p\\cdot n\\cdot \\log n)$$\\end{document} symbolic steps, where p is the number of colours and n the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to 248\\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}$$2^{48}$$\\end{document}) coloured graphs produced by models appearing in systems biology.", 
    "editor": [
      {
        "familyName": "Groote", 
        "givenName": "Jan Friso", 
        "type": "Person"
      }, 
      {
        "familyName": "Larsen", 
        "givenName": "Kim Guldstrand", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-72013-1_4", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-72012-4", 
        "978-3-030-72013-1"
      ], 
      "name": "Tools and Algorithms for the Construction and Analysis of Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "binary decision diagrams", 
      "symbolic algorithm", 
      "decision diagrams", 
      "connected components", 
      "number of colors", 
      "algorithm", 
      "number of vertices", 
      "graph", 
      "worst case", 
      "symbolic steps", 
      "original problem", 
      "colored graphs", 
      "experimental implementation", 
      "systems biology", 
      "edge-colored graph", 
      "scientific disciplines", 
      "vertices", 
      "implementation", 
      "detection", 
      "number", 
      "color", 
      "step", 
      "model", 
      "disciplines", 
      "components", 
      "decomposition", 
      "diagram", 
      "cases", 
      "scale", 
      "biology", 
      "problem"
    ], 
    "name": "Symbolic Coloured SCC Decomposition", 
    "pagination": "64-83", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1136573975"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-72013-1_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-72013-1_4", 
      "https://app.dimensions.ai/details/publication/pub.1136573975"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_230.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-72013-1_4"
  }
]
 

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-030-72013-1_4'

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-030-72013-1_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-72013-1_4'

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-030-72013-1_4'


 

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

117 TRIPLES      23 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-72013-1_4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N94bf29958789437bb941d7847377b793
4 schema:datePublished 2021-03-23
5 schema:datePublishedReg 2021-03-23
6 schema:description Problems arising in many scientific disciplines are often modelled using edge-coloured directed graphs. These can be enormous in the number of both vertices and colours. Given such a graph, the original problem frequently translates to the detection of the graph’s strongly connected components, which is challenging at this scale.We propose a new, symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs O(p·n·logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(p\cdot n\cdot \log n)$$\end{document} symbolic steps, where p is the number of colours and n the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to 248\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{48}$$\end{document}) coloured graphs produced by models appearing in systems biology.
7 schema:editor N69c51566df154ba8b32e7c9fd3ce8fca
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na4373a8cd3494f118873008883d488b4
12 schema:keywords algorithm
13 binary decision diagrams
14 biology
15 cases
16 color
17 colored graphs
18 components
19 connected components
20 decision diagrams
21 decomposition
22 detection
23 diagram
24 disciplines
25 edge-colored graph
26 experimental implementation
27 graph
28 implementation
29 model
30 number
31 number of colors
32 number of vertices
33 original problem
34 problem
35 scale
36 scientific disciplines
37 step
38 symbolic algorithm
39 symbolic steps
40 systems biology
41 vertices
42 worst case
43 schema:name Symbolic Coloured SCC Decomposition
44 schema:pagination 64-83
45 schema:productId N032dc2c1f4b0410d81774f0151081afc
46 Ne3385787d817474d95d8a9e03189e352
47 schema:publisher N27b8881c80c7481b9aaabf835a7a9dcf
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1136573975
49 https://doi.org/10.1007/978-3-030-72013-1_4
50 schema:sdDatePublished 2022-05-10T10:42
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher Ne0f0a10183764647bb302c8c301db943
53 schema:url https://doi.org/10.1007/978-3-030-72013-1_4
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N0276b41ceadf4af6a50609d9d6e016bc schema:familyName Larsen
58 schema:givenName Kim Guldstrand
59 rdf:type schema:Person
60 N032dc2c1f4b0410d81774f0151081afc schema:name doi
61 schema:value 10.1007/978-3-030-72013-1_4
62 rdf:type schema:PropertyValue
63 N275aa55a65c0472486aa6d95cdb0bf44 rdf:first sg:person.011410250615.43
64 rdf:rest rdf:nil
65 N27b8881c80c7481b9aaabf835a7a9dcf schema:name Springer Nature
66 rdf:type schema:Organisation
67 N3282d7cd96154cc4a5476b2546261b73 rdf:first N0276b41ceadf4af6a50609d9d6e016bc
68 rdf:rest rdf:nil
69 N5a44e868ccd049c8baf6eb30ae4f2af2 rdf:first sg:person.0645117057.83
70 rdf:rest Ne6bd843ef2484d91bbf1d67a084eb1ff
71 N69c51566df154ba8b32e7c9fd3ce8fca rdf:first Nbcb3c552700a42688bbbb4e1352a1e5a
72 rdf:rest N3282d7cd96154cc4a5476b2546261b73
73 N94bf29958789437bb941d7847377b793 rdf:first sg:person.014465763501.21
74 rdf:rest N5a44e868ccd049c8baf6eb30ae4f2af2
75 Na4373a8cd3494f118873008883d488b4 schema:isbn 978-3-030-72012-4
76 978-3-030-72013-1
77 schema:name Tools and Algorithms for the Construction and Analysis of Systems
78 rdf:type schema:Book
79 Nbcb3c552700a42688bbbb4e1352a1e5a schema:familyName Groote
80 schema:givenName Jan Friso
81 rdf:type schema:Person
82 Ne0f0a10183764647bb302c8c301db943 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Ne3385787d817474d95d8a9e03189e352 schema:name dimensions_id
85 schema:value pub.1136573975
86 rdf:type schema:PropertyValue
87 Ne6bd843ef2484d91bbf1d67a084eb1ff rdf:first sg:person.016130263073.10
88 rdf:rest N275aa55a65c0472486aa6d95cdb0bf44
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
93 schema:name Computation Theory and Mathematics
94 rdf:type schema:DefinedTerm
95 sg:person.011410250615.43 schema:affiliation grid-institutes:grid.10267.32
96 schema:familyName Šafránek
97 schema:givenName David
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011410250615.43
99 rdf:type schema:Person
100 sg:person.014465763501.21 schema:affiliation grid-institutes:grid.10267.32
101 schema:familyName Beneš
102 schema:givenName Nikola
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014465763501.21
104 rdf:type schema:Person
105 sg:person.016130263073.10 schema:affiliation grid-institutes:grid.10267.32
106 schema:familyName Pastva
107 schema:givenName Samuel
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016130263073.10
109 rdf:type schema:Person
110 sg:person.0645117057.83 schema:affiliation grid-institutes:grid.10267.32
111 schema:familyName Brim
112 schema:givenName Luboš
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0645117057.83
114 rdf:type schema:Person
115 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Brno, Czech Republic
116 schema:name Faculty of Informatics, Masaryk University, Brno, Czech Republic
117 rdf:type schema:Organization
 




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


...