Ontology type: schema:Chapter
2014
AUTHORSMichel Habib , Antoine Mamcarz
ABSTRACTWe 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... »
PAGES263-274
Graph-Theoretic Concepts in Computer Science
ISBN
978-3-319-12339-4
978-3-319-12340-0
http://scigraph.springernature.com/pub.10.1007/978-3-319-12340-0_22
DOIhttp://dx.doi.org/10.1007/978-3-319-12340-0_22
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1000713939
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
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