Independent Feedback Vertex Set for P5-Free Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-04

AUTHORS

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

ABSTRACT

The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer k≥0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P4-free graphs. We show that it remains polynomial-time solvable for P5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most k for a given integer k≥0. Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for H-free graphs with the complexity of 3-Colouring, Independent Odd Cycle Transversal and other related problems. More... »

PAGES

1-28

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-018-0474-x

DOI

http://dx.doi.org/10.1007/s00453-018-0474-x

DIMENSIONS

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


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": "French National Centre for Scientific Research", 
          "id": "https://www.grid.ac/institutes/grid.4444.0", 
          "name": [
            "LaBRI, CNRS, Bordeaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bonamy", 
        "givenName": "Marthe", 
        "id": "sg:person.013323417735.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013323417735.71"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Durham University", 
          "id": "https://www.grid.ac/institutes/grid.8250.f", 
          "name": [
            "Department of Computer Science, Durham University, Durham, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dabrowski", 
        "givenName": "Konrad K.", 
        "id": "sg:person.014351120542.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351120542.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Paris Diderot University", 
          "id": "https://www.grid.ac/institutes/grid.7452.4", 
          "name": [
            "IRIF, Universit\u00e9 Paris Diderot, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Feghali", 
        "givenName": "Carl", 
        "id": "sg:person.014701175477.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014701175477.94"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Durham University", 
          "id": "https://www.grid.ac/institutes/grid.8250.f", 
          "name": [
            "Department of Computer Science, Durham University, Durham, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Johnson", 
        "givenName": "Matthew", 
        "id": "sg:person.01352374000.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352374000.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Durham University", 
          "id": "https://www.grid.ac/institutes/grid.8250.f", 
          "name": [
            "Department of Computer Science, Durham University, Durham, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paulusma", 
        "givenName": "Dani\u00ebl", 
        "id": "sg:person.015664700463.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015664700463.05"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-45477-2_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000116606", 
          "https://doi.org/10.1007/3-540-45477-2_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45477-2_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000116606", 
          "https://doi.org/10.1007/3-540-45477-2_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-74759-0_178", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002658093", 
          "https://doi.org/10.1007/978-0-387-74759-0_178"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(80)90074-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006208571"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(86)90184-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007405434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(86)90184-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007405434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007977430", 
          "https://doi.org/10.1007/978-1-4684-2001-2_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.22028", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009019909"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02352694", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011653500", 
          "https://doi.org/10.1007/bf02352694"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02352694", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011653500", 
          "https://doi.org/10.1007/bf02352694"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2005.09.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012020894"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-008-9197-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015034684", 
          "https://doi.org/10.1007/s00453-008-9197-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-008-9197-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015034684", 
          "https://doi.org/10.1007/s00453-008-9197-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0028791", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015210853", 
          "https://doi.org/10.1007/bfb0028791"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0963548398003678", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016987698"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2008.01.021", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017911742"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2008.01.021", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017911742"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2014.05.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019714676"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(03)00446-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021923764"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(03)00446-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021923764"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-016-0150-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024510800", 
          "https://doi.org/10.1007/s00453-016-0150-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(90)90287-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028146377"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2012.11.031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032564288"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2500119", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036411616"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2012.10.030", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037162295"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00373-003-0540-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042051162", 
          "https://doi.org/10.1007/s00373-003-0540-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(93)90084-m", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047056282"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2012.02.012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047232260"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0012-365x(01)00335-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047772198"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9709-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052895612", 
          "https://doi.org/10.1007/s00453-012-9709-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0210055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841608"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1587/transfun.e98.a.1179", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1068091600"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2017.01.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084069678"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00493-017-3553-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085725994", 
          "https://doi.org/10.1007/s00493-017-3553-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2017.06.012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086257352"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973402.43", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.22182", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091497361"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2017.09.033", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092067569"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2017.11.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092801872"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer k\u22650, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P4-free graphs. We show that it remains polynomial-time solvable for P5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most k for a given integer k\u22650. Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for H-free graphs with the complexity of 3-Colouring, Independent Odd Cycle Transversal and other related problems.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-018-0474-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.2783135", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "81"
      }
    ], 
    "name": "Independent Feedback Vertex Set for P5-Free Graphs", 
    "pagination": "1-28", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a6b3aa6b42dd55dd1a0bd0299926f721f00a014d800f4f8e22fbfea0872254c8"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-018-0474-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105148686"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-018-0474-x", 
      "https://app.dimensions.ai/details/publication/pub.1105148686"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:18", 
    "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/0000000372_0000000372/records_117106_00000003.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-018-0474-x"
  }
]
 

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/s00453-018-0474-x'

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/s00453-018-0474-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0474-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-018-0474-x'


 

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

206 TRIPLES      21 PREDICATES      60 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-018-0474-x schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1de10bf020874171b7119bfb77d256e9
4 schema:citation sg:pub.10.1007/3-540-45477-2_23
5 sg:pub.10.1007/978-0-387-74759-0_178
6 sg:pub.10.1007/978-1-4684-2001-2_9
7 sg:pub.10.1007/bf02352694
8 sg:pub.10.1007/bfb0028791
9 sg:pub.10.1007/s00373-003-0540-1
10 sg:pub.10.1007/s00453-008-9197-8
11 sg:pub.10.1007/s00453-012-9709-4
12 sg:pub.10.1007/s00453-016-0150-y
13 sg:pub.10.1007/s00493-017-3553-8
14 https://doi.org/10.1002/jgt.22028
15 https://doi.org/10.1002/jgt.22182
16 https://doi.org/10.1016/0012-365x(90)90287-r
17 https://doi.org/10.1016/0020-0190(93)90084-m
18 https://doi.org/10.1016/0095-8956(80)90074-x
19 https://doi.org/10.1016/0304-3975(86)90184-2
20 https://doi.org/10.1016/j.dam.2008.01.021
21 https://doi.org/10.1016/j.disc.2005.09.016
22 https://doi.org/10.1016/j.disc.2012.11.031
23 https://doi.org/10.1016/j.disc.2017.01.006
24 https://doi.org/10.1016/j.ipl.2014.05.001
25 https://doi.org/10.1016/j.ipl.2017.11.004
26 https://doi.org/10.1016/j.tcs.2012.02.012
27 https://doi.org/10.1016/j.tcs.2012.10.030
28 https://doi.org/10.1016/j.tcs.2017.06.012
29 https://doi.org/10.1016/j.tcs.2017.09.033
30 https://doi.org/10.1016/s0012-365x(01)00335-1
31 https://doi.org/10.1016/s0166-218x(03)00446-3
32 https://doi.org/10.1017/s0963548398003678
33 https://doi.org/10.1137/0210055
34 https://doi.org/10.1137/1.9781611973402.43
35 https://doi.org/10.1145/2500119
36 https://doi.org/10.1587/transfun.e98.a.1179
37 schema:datePublished 2019-04
38 schema:datePublishedReg 2019-04-01
39 schema:description The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer k≥0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P4-free graphs. We show that it remains polynomial-time solvable for P5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most k for a given integer k≥0. Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for H-free graphs with the complexity of 3-Colouring, Independent Odd Cycle Transversal and other related problems.
40 schema:genre research_article
41 schema:inLanguage en
42 schema:isAccessibleForFree true
43 schema:isPartOf N45ae6b08b223484c89f1e129786cd6fb
44 N9e4ed7dfe87149e9a380bb792fcce22e
45 sg:journal.1047644
46 schema:name Independent Feedback Vertex Set for P5-Free Graphs
47 schema:pagination 1-28
48 schema:productId N86ad686ab1ac4a5d9bfdfd0f0ad2f19d
49 Na65889560ab141baa4fb23b4baf1483e
50 Nc333814672604a81b3afe5fc0fb5732d
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105148686
52 https://doi.org/10.1007/s00453-018-0474-x
53 schema:sdDatePublished 2019-04-11T14:18
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Nc50b6388e8454cc8bff20def880ba697
56 schema:url https://link.springer.com/10.1007%2Fs00453-018-0474-x
57 sgo:license sg:explorer/license/
58 sgo:sdDataset articles
59 rdf:type schema:ScholarlyArticle
60 N1de10bf020874171b7119bfb77d256e9 rdf:first sg:person.013323417735.71
61 rdf:rest N4dd31d7d5808437ab51c46fe6a15fe98
62 N45ae6b08b223484c89f1e129786cd6fb schema:volumeNumber 81
63 rdf:type schema:PublicationVolume
64 N4dd31d7d5808437ab51c46fe6a15fe98 rdf:first sg:person.014351120542.67
65 rdf:rest N95269996a36e45e9a7fdb3a5a22d8130
66 N6c776b6d0a304c128e0d1c994492da60 rdf:first sg:person.015664700463.05
67 rdf:rest rdf:nil
68 N86ad686ab1ac4a5d9bfdfd0f0ad2f19d schema:name dimensions_id
69 schema:value pub.1105148686
70 rdf:type schema:PropertyValue
71 N95269996a36e45e9a7fdb3a5a22d8130 rdf:first sg:person.014701175477.94
72 rdf:rest Nafc1dc39c5a64896b58acd20dbac017a
73 N9e4ed7dfe87149e9a380bb792fcce22e schema:issueNumber 4
74 rdf:type schema:PublicationIssue
75 Na65889560ab141baa4fb23b4baf1483e schema:name readcube_id
76 schema:value a6b3aa6b42dd55dd1a0bd0299926f721f00a014d800f4f8e22fbfea0872254c8
77 rdf:type schema:PropertyValue
78 Nafc1dc39c5a64896b58acd20dbac017a rdf:first sg:person.01352374000.86
79 rdf:rest N6c776b6d0a304c128e0d1c994492da60
80 Nc333814672604a81b3afe5fc0fb5732d schema:name doi
81 schema:value 10.1007/s00453-018-0474-x
82 rdf:type schema:PropertyValue
83 Nc50b6388e8454cc8bff20def880ba697 schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
89 schema:name Computation Theory and Mathematics
90 rdf:type schema:DefinedTerm
91 sg:grant.2783135 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-0474-x
92 rdf:type schema:MonetaryGrant
93 sg:journal.1047644 schema:issn 0178-4617
94 1432-0541
95 schema:name Algorithmica
96 rdf:type schema:Periodical
97 sg:person.013323417735.71 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
98 schema:familyName Bonamy
99 schema:givenName Marthe
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013323417735.71
101 rdf:type schema:Person
102 sg:person.01352374000.86 schema:affiliation https://www.grid.ac/institutes/grid.8250.f
103 schema:familyName Johnson
104 schema:givenName Matthew
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352374000.86
106 rdf:type schema:Person
107 sg:person.014351120542.67 schema:affiliation https://www.grid.ac/institutes/grid.8250.f
108 schema:familyName Dabrowski
109 schema:givenName Konrad K.
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351120542.67
111 rdf:type schema:Person
112 sg:person.014701175477.94 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
113 schema:familyName Feghali
114 schema:givenName Carl
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014701175477.94
116 rdf:type schema:Person
117 sg:person.015664700463.05 schema:affiliation https://www.grid.ac/institutes/grid.8250.f
118 schema:familyName Paulusma
119 schema:givenName Daniël
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015664700463.05
121 rdf:type schema:Person
122 sg:pub.10.1007/3-540-45477-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000116606
123 https://doi.org/10.1007/3-540-45477-2_23
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/978-0-387-74759-0_178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002658093
126 https://doi.org/10.1007/978-0-387-74759-0_178
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
129 https://doi.org/10.1007/978-1-4684-2001-2_9
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/bf02352694 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011653500
132 https://doi.org/10.1007/bf02352694
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/bfb0028791 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015210853
135 https://doi.org/10.1007/bfb0028791
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s00373-003-0540-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042051162
138 https://doi.org/10.1007/s00373-003-0540-1
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s00453-008-9197-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015034684
141 https://doi.org/10.1007/s00453-008-9197-8
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/s00453-012-9709-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052895612
144 https://doi.org/10.1007/s00453-012-9709-4
145 rdf:type schema:CreativeWork
146 sg:pub.10.1007/s00453-016-0150-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1024510800
147 https://doi.org/10.1007/s00453-016-0150-y
148 rdf:type schema:CreativeWork
149 sg:pub.10.1007/s00493-017-3553-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085725994
150 https://doi.org/10.1007/s00493-017-3553-8
151 rdf:type schema:CreativeWork
152 https://doi.org/10.1002/jgt.22028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009019909
153 rdf:type schema:CreativeWork
154 https://doi.org/10.1002/jgt.22182 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091497361
155 rdf:type schema:CreativeWork
156 https://doi.org/10.1016/0012-365x(90)90287-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1028146377
157 rdf:type schema:CreativeWork
158 https://doi.org/10.1016/0020-0190(93)90084-m schema:sameAs https://app.dimensions.ai/details/publication/pub.1047056282
159 rdf:type schema:CreativeWork
160 https://doi.org/10.1016/0095-8956(80)90074-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1006208571
161 rdf:type schema:CreativeWork
162 https://doi.org/10.1016/0304-3975(86)90184-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007405434
163 rdf:type schema:CreativeWork
164 https://doi.org/10.1016/j.dam.2008.01.021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017911742
165 rdf:type schema:CreativeWork
166 https://doi.org/10.1016/j.disc.2005.09.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012020894
167 rdf:type schema:CreativeWork
168 https://doi.org/10.1016/j.disc.2012.11.031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032564288
169 rdf:type schema:CreativeWork
170 https://doi.org/10.1016/j.disc.2017.01.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084069678
171 rdf:type schema:CreativeWork
172 https://doi.org/10.1016/j.ipl.2014.05.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019714676
173 rdf:type schema:CreativeWork
174 https://doi.org/10.1016/j.ipl.2017.11.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092801872
175 rdf:type schema:CreativeWork
176 https://doi.org/10.1016/j.tcs.2012.02.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047232260
177 rdf:type schema:CreativeWork
178 https://doi.org/10.1016/j.tcs.2012.10.030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037162295
179 rdf:type schema:CreativeWork
180 https://doi.org/10.1016/j.tcs.2017.06.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086257352
181 rdf:type schema:CreativeWork
182 https://doi.org/10.1016/j.tcs.2017.09.033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092067569
183 rdf:type schema:CreativeWork
184 https://doi.org/10.1016/s0012-365x(01)00335-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047772198
185 rdf:type schema:CreativeWork
186 https://doi.org/10.1016/s0166-218x(03)00446-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021923764
187 rdf:type schema:CreativeWork
188 https://doi.org/10.1017/s0963548398003678 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016987698
189 rdf:type schema:CreativeWork
190 https://doi.org/10.1137/0210055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841608
191 rdf:type schema:CreativeWork
192 https://doi.org/10.1137/1.9781611973402.43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801866
193 rdf:type schema:CreativeWork
194 https://doi.org/10.1145/2500119 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036411616
195 rdf:type schema:CreativeWork
196 https://doi.org/10.1587/transfun.e98.a.1179 schema:sameAs https://app.dimensions.ai/details/publication/pub.1068091600
197 rdf:type schema:CreativeWork
198 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
199 schema:name LaBRI, CNRS, Bordeaux, France
200 rdf:type schema:Organization
201 https://www.grid.ac/institutes/grid.7452.4 schema:alternateName Paris Diderot University
202 schema:name IRIF, Université Paris Diderot, Paris, France
203 rdf:type schema:Organization
204 https://www.grid.ac/institutes/grid.8250.f schema:alternateName Durham University
205 schema:name Department of Computer Science, Durham University, Durham, UK
206 rdf:type schema:Organization
 




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


...