Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-01

AUTHORS

Neeldhara Misra, Fahad Panolan, Ashutosh Rai, Venkatesh Raman, Saket Saurabh

ABSTRACT

We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133–137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an nO(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by ℓ, the number of vertices in the solution, we give two fixed-parameter tractable algorithms.The first algorithm runs in time 5.44ℓ(n+t)O(1) where t is the number of maximal independent sets of the input graph.The second algorithm runs in time O(6.75ℓ+o(ℓ)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense:On split graphs, we do not expect a polynomial kernel if q is a part of the input.On perfect graphs, we do not expect a polynomial kernel even for fixed values of q≥2. The first algorithm runs in time 5.44ℓ(n+t)O(1) where t is the number of maximal independent sets of the input graph. The second algorithm runs in time O(6.75ℓ+o(ℓ)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time. On split graphs, we do not expect a polynomial kernel if q is a part of the input. On perfect graphs, we do not expect a polynomial kernel even for fixed values of q≥2. More... »

PAGES

26-46

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-018-0431-8

DOI

http://dx.doi.org/10.1007/s00453-018-0431-8

DIMENSIONS

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


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": "Indian Institute of Technology Gandhinagar", 
          "id": "https://www.grid.ac/institutes/grid.462384.f", 
          "name": [
            "Indian Institute of Technology, Gandhinagar, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Misra", 
        "givenName": "Neeldhara", 
        "id": "sg:person.012615050301.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012615050301.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Bergen", 
          "id": "https://www.grid.ac/institutes/grid.7914.b", 
          "name": [
            "University of Bergen, Bergen, Norway"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Panolan", 
        "givenName": "Fahad", 
        "id": "sg:person.012007106135.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012007106135.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.462414.1", 
          "name": [
            "The Institute of Mathematical Sciences, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rai", 
        "givenName": "Ashutosh", 
        "id": "sg:person.016203230121.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016203230121.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.462414.1", 
          "name": [
            "The Institute of Mathematical Sciences, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raman", 
        "givenName": "Venkatesh", 
        "id": "sg:person.015145675270.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015145675270.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Bergen", 
          "id": "https://www.grid.ac/institutes/grid.7914.b", 
          "name": [
            "The Institute of Mathematical Sciences, Chennai, India", 
            "University of Bergen, Bergen, Norway"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saurabh", 
        "givenName": "Saket", 
        "id": "sg:person.014061711675.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014061711675.71"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/2635810", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001418417"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/plms/s2-17.1.75", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009143639"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1233481.1233493", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011974863"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9148-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013922814", 
          "https://doi.org/10.1007/s00453-007-9148-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9148-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013922814", 
          "https://doi.org/10.1007/s00453-007-9148-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1250790.1250801", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014492884"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(01)00414-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017243341"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2010.06.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018586756"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(87)90107-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019621406"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(87)90107-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019621406"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-015-0083-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021991734", 
          "https://doi.org/10.1007/s00453-015-0083-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-11269-0_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028791184", 
          "https://doi.org/10.1007/978-3-642-11269-0_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-11269-0_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028791184", 
          "https://doi.org/10.1007/978-3-642-11269-0_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-48054-0_43", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031345254", 
          "https://doi.org/10.1007/978-3-662-48054-0_43"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230190206", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035012471"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.orl.2004.03.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035440472"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-007-1334-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035920328", 
          "https://doi.org/10.1007/s00224-007-1334-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2629620", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037761533"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-010-9428-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039108485", 
          "https://doi.org/10.1007/s00453-010-9428-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2886094", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043584846"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9152-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045820987", 
          "https://doi.org/10.1007/s00453-007-9152-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-007-9152-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045820987", 
          "https://doi.org/10.1007/s00453-007-9152-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2009.04.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046558319"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2008.08.020", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048269333"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2973749", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048879347"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1050354225", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-0515-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050354225", 
          "https://doi.org/10.1007/978-1-4612-0515-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-0515-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050354225", 
          "https://doi.org/10.1007/978-1-4612-0515-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2650261", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051627555"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-013-9837-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053350744", 
          "https://doi.org/10.1007/s00453-013-9837-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0206036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841375"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/09077850x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062856947"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973075.43", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801225"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-017-9805-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091557501", 
          "https://doi.org/10.1007/s00224-017-9805-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2017.09.012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092128890"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1995.492475", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093736028"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2012.46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094117164"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/acprof:oso/9780198566076.001.0001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098761640"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-01", 
    "datePublishedReg": "2019-01-01", 
    "description": "We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133\u2013137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an nO(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by \u2113, the number of vertices in the solution, we give two fixed-parameter tractable algorithms.The first algorithm runs in time 5.44\u2113(n+t)O(1) where t is the number of maximal independent sets of the input graph.The second algorithm runs in time O(6.75\u2113+o(\u2113)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense:On split graphs, we do not expect a polynomial kernel if q is a part of the input.On perfect graphs, we do not expect a polynomial kernel even for fixed values of q\u22652. The first algorithm runs in time 5.44\u2113(n+t)O(1) where t is the number of maximal independent sets of the input graph. The second algorithm runs in time O(6.75\u2113+o(\u2113)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time. On split graphs, we do not expect a polynomial kernel if q is a part of the input. On perfect graphs, we do not expect a polynomial kernel even for fixed values of q\u22652.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-018-0431-8", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3795456", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "81"
      }
    ], 
    "name": "Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs", 
    "pagination": "26-46", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f4619b7dd7360d5cf1cf27300bb930b1038a91d64705e424ff23e5aaa4995328"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-018-0431-8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1103183208"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-018-0431-8", 
      "https://app.dimensions.ai/details/publication/pub.1103183208"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:21", 
    "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_117125_00000003.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-018-0431-8"
  }
]
 

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-0431-8'

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-0431-8'

Turtle is a human-readable linked data format.

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

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-0431-8'


 

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-0431-8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N55bb4d2fe96f4b1f90b18f71f91dbfe5
4 schema:citation sg:pub.10.1007/978-1-4612-0515-9
5 sg:pub.10.1007/978-3-642-11269-0_2
6 sg:pub.10.1007/978-3-662-48054-0_43
7 sg:pub.10.1007/s00224-007-1334-2
8 sg:pub.10.1007/s00224-017-9805-6
9 sg:pub.10.1007/s00453-007-9148-9
10 sg:pub.10.1007/s00453-007-9152-0
11 sg:pub.10.1007/s00453-010-9428-7
12 sg:pub.10.1007/s00453-013-9837-5
13 sg:pub.10.1007/s00453-015-0083-x
14 https://app.dimensions.ai/details/publication/pub.1050354225
15 https://doi.org/10.1002/net.3230190206
16 https://doi.org/10.1016/0020-0190(87)90107-4
17 https://doi.org/10.1016/j.dam.2008.08.020
18 https://doi.org/10.1016/j.disc.2017.09.012
19 https://doi.org/10.1016/j.jcss.2009.04.001
20 https://doi.org/10.1016/j.jcss.2010.06.007
21 https://doi.org/10.1016/j.orl.2004.03.002
22 https://doi.org/10.1016/s0304-3975(01)00414-5
23 https://doi.org/10.1093/acprof:oso/9780198566076.001.0001
24 https://doi.org/10.1109/focs.2012.46
25 https://doi.org/10.1109/sfcs.1995.492475
26 https://doi.org/10.1112/plms/s2-17.1.75
27 https://doi.org/10.1137/0206036
28 https://doi.org/10.1137/09077850x
29 https://doi.org/10.1137/1.9781611973075.43
30 https://doi.org/10.1145/1233481.1233493
31 https://doi.org/10.1145/1250790.1250801
32 https://doi.org/10.1145/2629620
33 https://doi.org/10.1145/2635810
34 https://doi.org/10.1145/2650261
35 https://doi.org/10.1145/2886094
36 https://doi.org/10.1145/2973749
37 schema:datePublished 2019-01
38 schema:datePublishedReg 2019-01-01
39 schema:description We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133–137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an nO(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by ℓ, the number of vertices in the solution, we give two fixed-parameter tractable algorithms.The first algorithm runs in time 5.44ℓ(n+t)O(1) where t is the number of maximal independent sets of the input graph.The second algorithm runs in time O(6.75ℓ+o(ℓ)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense:On split graphs, we do not expect a polynomial kernel if q is a part of the input.On perfect graphs, we do not expect a polynomial kernel even for fixed values of q≥2. The first algorithm runs in time 5.44ℓ(n+t)O(1) where t is the number of maximal independent sets of the input graph. The second algorithm runs in time O(6.75ℓ+o(ℓ)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time. On split graphs, we do not expect a polynomial kernel if q is a part of the input. On perfect graphs, we do not expect a polynomial kernel even for fixed values of q≥2.
40 schema:genre research_article
41 schema:inLanguage en
42 schema:isAccessibleForFree false
43 schema:isPartOf Na308b6abc77c4b3ca552adb29343095d
44 Nacac66d4a1a749b1b5b1805ce54de0ed
45 sg:journal.1047644
46 schema:name Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
47 schema:pagination 26-46
48 schema:productId N55db21ca175e483b848c6f9442ebb1bf
49 Nd0d0fec3635e4b47af79abc693dbae64
50 Ndae9e73e2d29454bbfa0fb7b40c1cb63
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103183208
52 https://doi.org/10.1007/s00453-018-0431-8
53 schema:sdDatePublished 2019-04-11T14:21
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Ncac35d77460440868d91d26698c84c0c
56 schema:url https://link.springer.com/10.1007%2Fs00453-018-0431-8
57 sgo:license sg:explorer/license/
58 sgo:sdDataset articles
59 rdf:type schema:ScholarlyArticle
60 N04ab9d4144eb4d04be0f54d371efc03c rdf:first sg:person.016203230121.49
61 rdf:rest Nf27f8c284f0449709940a006d0e51002
62 N55bb4d2fe96f4b1f90b18f71f91dbfe5 rdf:first sg:person.012615050301.31
63 rdf:rest Nf88b5f41c5dd4537adfa274d4caaedbc
64 N55db21ca175e483b848c6f9442ebb1bf schema:name readcube_id
65 schema:value f4619b7dd7360d5cf1cf27300bb930b1038a91d64705e424ff23e5aaa4995328
66 rdf:type schema:PropertyValue
67 Na308b6abc77c4b3ca552adb29343095d schema:volumeNumber 81
68 rdf:type schema:PublicationVolume
69 Nacac66d4a1a749b1b5b1805ce54de0ed schema:issueNumber 1
70 rdf:type schema:PublicationIssue
71 Nb2a12f4ce4c4445d9810af24e9a30752 rdf:first sg:person.014061711675.71
72 rdf:rest rdf:nil
73 Ncac35d77460440868d91d26698c84c0c schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 Nd0d0fec3635e4b47af79abc693dbae64 schema:name doi
76 schema:value 10.1007/s00453-018-0431-8
77 rdf:type schema:PropertyValue
78 Ndae9e73e2d29454bbfa0fb7b40c1cb63 schema:name dimensions_id
79 schema:value pub.1103183208
80 rdf:type schema:PropertyValue
81 Nf27f8c284f0449709940a006d0e51002 rdf:first sg:person.015145675270.07
82 rdf:rest Nb2a12f4ce4c4445d9810af24e9a30752
83 Nf88b5f41c5dd4537adfa274d4caaedbc rdf:first sg:person.012007106135.58
84 rdf:rest N04ab9d4144eb4d04be0f54d371efc03c
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.3795456 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-018-0431-8
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.012007106135.58 schema:affiliation https://www.grid.ac/institutes/grid.7914.b
98 schema:familyName Panolan
99 schema:givenName Fahad
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012007106135.58
101 rdf:type schema:Person
102 sg:person.012615050301.31 schema:affiliation https://www.grid.ac/institutes/grid.462384.f
103 schema:familyName Misra
104 schema:givenName Neeldhara
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012615050301.31
106 rdf:type schema:Person
107 sg:person.014061711675.71 schema:affiliation https://www.grid.ac/institutes/grid.7914.b
108 schema:familyName Saurabh
109 schema:givenName Saket
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014061711675.71
111 rdf:type schema:Person
112 sg:person.015145675270.07 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
113 schema:familyName Raman
114 schema:givenName Venkatesh
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015145675270.07
116 rdf:type schema:Person
117 sg:person.016203230121.49 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
118 schema:familyName Rai
119 schema:givenName Ashutosh
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016203230121.49
121 rdf:type schema:Person
122 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
123 https://doi.org/10.1007/978-1-4612-0515-9
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/978-3-642-11269-0_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028791184
126 https://doi.org/10.1007/978-3-642-11269-0_2
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/978-3-662-48054-0_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031345254
129 https://doi.org/10.1007/978-3-662-48054-0_43
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/s00224-007-1334-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035920328
132 https://doi.org/10.1007/s00224-007-1334-2
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/s00224-017-9805-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091557501
135 https://doi.org/10.1007/s00224-017-9805-6
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s00453-007-9148-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013922814
138 https://doi.org/10.1007/s00453-007-9148-9
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s00453-007-9152-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045820987
141 https://doi.org/10.1007/s00453-007-9152-0
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/s00453-010-9428-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039108485
144 https://doi.org/10.1007/s00453-010-9428-7
145 rdf:type schema:CreativeWork
146 sg:pub.10.1007/s00453-013-9837-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053350744
147 https://doi.org/10.1007/s00453-013-9837-5
148 rdf:type schema:CreativeWork
149 sg:pub.10.1007/s00453-015-0083-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1021991734
150 https://doi.org/10.1007/s00453-015-0083-x
151 rdf:type schema:CreativeWork
152 https://app.dimensions.ai/details/publication/pub.1050354225 schema:CreativeWork
153 https://doi.org/10.1002/net.3230190206 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035012471
154 rdf:type schema:CreativeWork
155 https://doi.org/10.1016/0020-0190(87)90107-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019621406
156 rdf:type schema:CreativeWork
157 https://doi.org/10.1016/j.dam.2008.08.020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048269333
158 rdf:type schema:CreativeWork
159 https://doi.org/10.1016/j.disc.2017.09.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092128890
160 rdf:type schema:CreativeWork
161 https://doi.org/10.1016/j.jcss.2009.04.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046558319
162 rdf:type schema:CreativeWork
163 https://doi.org/10.1016/j.jcss.2010.06.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018586756
164 rdf:type schema:CreativeWork
165 https://doi.org/10.1016/j.orl.2004.03.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035440472
166 rdf:type schema:CreativeWork
167 https://doi.org/10.1016/s0304-3975(01)00414-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017243341
168 rdf:type schema:CreativeWork
169 https://doi.org/10.1093/acprof:oso/9780198566076.001.0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098761640
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1109/focs.2012.46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094117164
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1109/sfcs.1995.492475 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093736028
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1112/plms/s2-17.1.75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009143639
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1137/0206036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841375
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1137/09077850x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856947
180 rdf:type schema:CreativeWork
181 https://doi.org/10.1137/1.9781611973075.43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801225
182 rdf:type schema:CreativeWork
183 https://doi.org/10.1145/1233481.1233493 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011974863
184 rdf:type schema:CreativeWork
185 https://doi.org/10.1145/1250790.1250801 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014492884
186 rdf:type schema:CreativeWork
187 https://doi.org/10.1145/2629620 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037761533
188 rdf:type schema:CreativeWork
189 https://doi.org/10.1145/2635810 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001418417
190 rdf:type schema:CreativeWork
191 https://doi.org/10.1145/2650261 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051627555
192 rdf:type schema:CreativeWork
193 https://doi.org/10.1145/2886094 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043584846
194 rdf:type schema:CreativeWork
195 https://doi.org/10.1145/2973749 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048879347
196 rdf:type schema:CreativeWork
197 https://www.grid.ac/institutes/grid.462384.f schema:alternateName Indian Institute of Technology Gandhinagar
198 schema:name Indian Institute of Technology, Gandhinagar, India
199 rdf:type schema:Organization
200 https://www.grid.ac/institutes/grid.462414.1 schema:alternateName Institute of Mathematical Sciences
201 schema:name The Institute of Mathematical Sciences, Chennai, India
202 rdf:type schema:Organization
203 https://www.grid.ac/institutes/grid.7914.b schema:alternateName University of Bergen
204 schema:name The Institute of Mathematical Sciences, Chennai, India
205 University of Bergen, Bergen, Norway
206 rdf:type schema:Organization
 




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


...