Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Michel Habib , Antoine Mamcarz

ABSTRACT

We introduce the colored decompositions framework, in which vertices of the graph can be equipped with colors, and in which the goal is to find decompositions of this graph that do not separate the color classes. In this paper, we give two linear time algorithms for the colored modular and split decompositions of graphs, and we apply them to give linear time algorithms for the modular and split decompositions of trigraphs, which improves a result of Thomassé, Trotignon and Vuskovic (2013). As a byproduct, we introduce the non-separating families that allow us to prove that those two decompositions have the same properties on graphs and on trigraphs. More... »

PAGES

263-274

References to SciGraph publications

  • 1967-03. Transitiv orientierbare Graphen in ACTA MATHEMATICA
  • 1994. A new linear algorithm for Modular Decomposition in TREES IN ALGEBRA AND PROGRAMMING — CAAP'94
  • 2008. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1994. Efficient parallel and linear time sequential split decomposition (extended abstract) in FOUNDATION OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 2014-10. Computing H-Joins with Application to 2-Modular Decomposition in ALGORITHMICA
  • Book

    TITLE

    Graph-Theoretic Concepts in Computer Science

    ISBN

    978-3-319-12339-4
    978-3-319-12340-0

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-12340-0_22

    DOI

    http://dx.doi.org/10.1007/978-3-319-12340-0_22

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Paris Diderot University", 
              "id": "https://www.grid.ac/institutes/grid.7452.4", 
              "name": [
                "CNRS and Universit\u00e9 Paris Diderot - Paris 7"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Habib", 
            "givenName": "Michel", 
            "id": "sg:person.012600773121.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600773121.44"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Paris Diderot University", 
              "id": "https://www.grid.ac/institutes/grid.7452.4", 
              "name": [
                "CNRS and Universit\u00e9 Paris Diderot - Paris 7"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mamcarz", 
            "givenName": "Antoine", 
            "id": "sg:person.014536045406.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014536045406.19"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0020-0190(98)00076-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000728435"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejc.2011.09.032", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005422865"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02020961", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005931527", 
              "https://doi.org/10.1007/bf02020961"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02020961", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005931527", 
              "https://doi.org/10.1007/bf02020961"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2011.07.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007662780"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.20405", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008659640"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.20405", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008659640"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-013-9820-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009916277", 
              "https://doi.org/10.1007/s00453-013-9820-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70575-8_52", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010918995", 
              "https://doi.org/10.1007/978-3-540-70575-8_52"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.2000.1090", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011050685"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-58715-2_123", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011748171", 
              "https://doi.org/10.1007/3-540-58715-2_123"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0012-365x(98)00319-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023976490"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(81)90138-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025763689"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0017474", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027554619", 
              "https://doi.org/10.1007/bfb0017474"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2015.04.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035274233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2015.04.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035274233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2015.04.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035274233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2015.04.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035274233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.20040", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035396928"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2007.06.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048570847"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/10080052x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062859074"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4153/cjm-1980-057-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072266654"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014", 
        "datePublishedReg": "2014-01-01", 
        "description": "We introduce the colored decompositions framework, in which vertices of the graph can be equipped with colors, and in which\u00a0the goal is to find decompositions of this graph that do not separate the color classes. In this paper, we give two linear time algorithms for the colored modular and split decompositions of graphs, and we apply them to give linear time algorithms for the modular and split decompositions of trigraphs, which improves a result of Thomass\u00e9, Trotignon and Vuskovic (2013). As a byproduct, we introduce the non-separating families that allow us to prove that those two decompositions have the same properties on graphs and on trigraphs.", 
        "editor": [
          {
            "familyName": "Kratsch", 
            "givenName": "Dieter", 
            "type": "Person"
          }, 
          {
            "familyName": "Todinca", 
            "givenName": "Ioan", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-12340-0_22", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-12339-4", 
            "978-3-319-12340-0"
          ], 
          "name": "Graph-Theoretic Concepts in Computer Science", 
          "type": "Book"
        }, 
        "name": "Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs", 
        "pagination": "263-274", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-12340-0_22"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "036669fe89f0af64990b98a3de64a4b2194178ef1607fecd52f3ac391e68bf3c"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1000713939"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-12340-0_22", 
          "https://app.dimensions.ai/details/publication/pub.1000713939"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T18:07", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8681_00000243.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-12340-0_22"
      }
    ]
     

    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-319-12340-0_22'

    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-319-12340-0_22'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-12340-0_22'

    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-319-12340-0_22'


     

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

    133 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-12340-0_22 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N414a24aa611a46f892797302de2ad441
    4 schema:citation sg:pub.10.1007/3-540-58715-2_123
    5 sg:pub.10.1007/978-3-540-70575-8_52
    6 sg:pub.10.1007/bf02020961
    7 sg:pub.10.1007/bfb0017474
    8 sg:pub.10.1007/s00453-013-9820-1
    9 https://doi.org/10.1002/jgt.20040
    10 https://doi.org/10.1002/jgt.20405
    11 https://doi.org/10.1006/jagm.2000.1090
    12 https://doi.org/10.1016/0012-365x(81)90138-2
    13 https://doi.org/10.1016/j.ejc.2011.09.032
    14 https://doi.org/10.1016/j.jctb.2007.06.007
    15 https://doi.org/10.1016/j.jctb.2011.07.003
    16 https://doi.org/10.1016/j.jctb.2015.04.007
    17 https://doi.org/10.1016/s0012-365x(98)00319-7
    18 https://doi.org/10.1016/s0020-0190(98)00076-3
    19 https://doi.org/10.1137/10080052x
    20 https://doi.org/10.4153/cjm-1980-057-7
    21 schema:datePublished 2014
    22 schema:datePublishedReg 2014-01-01
    23 schema:description We introduce the colored decompositions framework, in which vertices of the graph can be equipped with colors, and in which the goal is to find decompositions of this graph that do not separate the color classes. In this paper, we give two linear time algorithms for the colored modular and split decompositions of graphs, and we apply them to give linear time algorithms for the modular and split decompositions of trigraphs, which improves a result of Thomassé, Trotignon and Vuskovic (2013). As a byproduct, we introduce the non-separating families that allow us to prove that those two decompositions have the same properties on graphs and on trigraphs.
    24 schema:editor Ndb20292bb7764254bea99e2716484f8b
    25 schema:genre chapter
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf N710f92b6cf204179af425f30ebcd9f53
    29 schema:name Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs
    30 schema:pagination 263-274
    31 schema:productId N1831ff52c87a4e4194d57b39bfc2f0a8
    32 N295274605cf44034b09e9a6f617504ee
    33 N6a8288eaa2234bfcb8a374be07546531
    34 schema:publisher Nea57d46a3e4942f8b492906de03b1876
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000713939
    36 https://doi.org/10.1007/978-3-319-12340-0_22
    37 schema:sdDatePublished 2019-04-15T18:07
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher N7070040063764d5485bf122781871242
    40 schema:url http://link.springer.com/10.1007/978-3-319-12340-0_22
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset chapters
    43 rdf:type schema:Chapter
    44 N1831ff52c87a4e4194d57b39bfc2f0a8 schema:name doi
    45 schema:value 10.1007/978-3-319-12340-0_22
    46 rdf:type schema:PropertyValue
    47 N295274605cf44034b09e9a6f617504ee schema:name readcube_id
    48 schema:value 036669fe89f0af64990b98a3de64a4b2194178ef1607fecd52f3ac391e68bf3c
    49 rdf:type schema:PropertyValue
    50 N3d3c479dc265432abe5363e8c288f8b7 schema:familyName Kratsch
    51 schema:givenName Dieter
    52 rdf:type schema:Person
    53 N414a24aa611a46f892797302de2ad441 rdf:first sg:person.012600773121.44
    54 rdf:rest Nde452041c5a244db9000e55c97c930d9
    55 N5190e3d36b754ef4be3857c202abc408 rdf:first N9b287be2ea8942fb8c1452be0a91e97d
    56 rdf:rest rdf:nil
    57 N6a8288eaa2234bfcb8a374be07546531 schema:name dimensions_id
    58 schema:value pub.1000713939
    59 rdf:type schema:PropertyValue
    60 N7070040063764d5485bf122781871242 schema:name Springer Nature - SN SciGraph project
    61 rdf:type schema:Organization
    62 N710f92b6cf204179af425f30ebcd9f53 schema:isbn 978-3-319-12339-4
    63 978-3-319-12340-0
    64 schema:name Graph-Theoretic Concepts in Computer Science
    65 rdf:type schema:Book
    66 N9b287be2ea8942fb8c1452be0a91e97d schema:familyName Todinca
    67 schema:givenName Ioan
    68 rdf:type schema:Person
    69 Ndb20292bb7764254bea99e2716484f8b rdf:first N3d3c479dc265432abe5363e8c288f8b7
    70 rdf:rest N5190e3d36b754ef4be3857c202abc408
    71 Nde452041c5a244db9000e55c97c930d9 rdf:first sg:person.014536045406.19
    72 rdf:rest rdf:nil
    73 Nea57d46a3e4942f8b492906de03b1876 schema:location Cham
    74 schema:name Springer International Publishing
    75 rdf:type schema:Organisation
    76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Information and Computing Sciences
    78 rdf:type schema:DefinedTerm
    79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Computation Theory and Mathematics
    81 rdf:type schema:DefinedTerm
    82 sg:person.012600773121.44 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
    83 schema:familyName Habib
    84 schema:givenName Michel
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600773121.44
    86 rdf:type schema:Person
    87 sg:person.014536045406.19 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
    88 schema:familyName Mamcarz
    89 schema:givenName Antoine
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014536045406.19
    91 rdf:type schema:Person
    92 sg:pub.10.1007/3-540-58715-2_123 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011748171
    93 https://doi.org/10.1007/3-540-58715-2_123
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-3-540-70575-8_52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010918995
    96 https://doi.org/10.1007/978-3-540-70575-8_52
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/bf02020961 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005931527
    99 https://doi.org/10.1007/bf02020961
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bfb0017474 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027554619
    102 https://doi.org/10.1007/bfb0017474
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/s00453-013-9820-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009916277
    105 https://doi.org/10.1007/s00453-013-9820-1
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1002/jgt.20040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035396928
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1002/jgt.20405 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008659640
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1006/jagm.2000.1090 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011050685
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/0012-365x(81)90138-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025763689
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/j.ejc.2011.09.032 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005422865
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/j.jctb.2007.06.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048570847
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/j.jctb.2011.07.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007662780
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1016/j.jctb.2015.04.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035274233
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1016/s0012-365x(98)00319-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023976490
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1016/s0020-0190(98)00076-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000728435
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1137/10080052x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062859074
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.4153/cjm-1980-057-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266654
    130 rdf:type schema:CreativeWork
    131 https://www.grid.ac/institutes/grid.7452.4 schema:alternateName Paris Diderot University
    132 schema:name CNRS and Université Paris Diderot - Paris 7
    133 rdf:type schema:Organization
     




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


    ...