On the Parameterized Complexity of Contraction to Generalization of Trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-04

AUTHORS

Akanksha Agarwal, Saket Saurabh, Prafullkumar Tale

ABSTRACT

For a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S ⊆ E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al. [Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a “parameterized way”. Let Tℓ be the family of graphs such that each graph in Tℓ can be made into a tree by deleting at most ℓ edges. Thus, the problem we study is Tℓ-Contraction. We design an FPT algorithm for Tℓ-Contraction running in time O((2ℓ+2)O(k+ℓ)⋅nO(1)). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for Tℓ-Contraction of size O([k(k+2ℓ)](⌈αα−1⌉+1)). More... »

PAGES

1-28

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-018-9892-z

DOI

http://dx.doi.org/10.1007/s00224-018-9892-z

DIMENSIONS

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


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": "University of Bergen", 
          "id": "https://www.grid.ac/institutes/grid.7914.b", 
          "name": [
            "Department of Informatics, University of Bergen, Bergen, Norway"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Agarwal", 
        "givenName": "Akanksha", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.462414.1", 
          "name": [
            "Department of Informatics, University of Bergen, Bergen, Norway", 
            "The Institute of Mathematical Sciences, HBNI, Chennai, India"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.462414.1", 
          "name": [
            "The Institute of Mathematical Sciences, HBNI, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tale", 
        "givenName": "Prafullkumar", 
        "id": "sg:person.011047776661.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011047776661.38"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(96)00050-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002138261"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1004947649", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21275-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004947649", 
          "https://doi.org/10.1007/978-3-319-21275-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21275-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004947649", 
          "https://doi.org/10.1007/978-3-319-21275-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1005955659", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4471-5559-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005955659", 
          "https://doi.org/10.1007/978-1-4471-5559-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4471-5559-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005955659", 
          "https://doi.org/10.1007/978-1-4471-5559-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2011.04.039", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006206581"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-03898-8_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007774141", 
          "https://doi.org/10.1007/978-3-319-03898-8_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-31155-0_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009449672", 
          "https://doi.org/10.1007/978-3-642-31155-0_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(83)90012-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009598816"
        ], 
        "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": "sg:pub.10.1007/s00236-014-0204-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020716903", 
          "https://doi.org/10.1007/s00236-014-0204-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2013.09.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030715475"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2016.06.012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033495471"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-03898-8_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036594137", 
          "https://doi.org/10.1007/978-3-319-03898-8_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2012.12.041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040706843"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9670-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042020468", 
          "https://doi.org/10.1007/s00453-012-9670-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(83)90101-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042950542"
        ], 
        "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/0166-218x(81)90039-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048629933"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/130907392", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062870408"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-57586-5_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084851738", 
          "https://doi.org/10.1007/978-3-319-57586-5_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3055399.3055456", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091880551"
        ], 
        "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.2011.23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095593381"
        ], 
        "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-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "For a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S \u2286 E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al. [Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a \u201cparameterized way\u201d. Let T\u2113 be the family of graphs such that each graph in T\u2113 can be made into a tree by deleting at most \u2113 edges. Thus, the problem we study is T\u2113-Contraction. We design an FPT algorithm for T\u2113-Contraction running in time O((2\u2113+2)O(k+\u2113)\u22c5nO(1)). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for T\u2113-Contraction of size O([k(k+2\u2113)](\u2308\u03b1\u03b1\u22121\u2309+1)).", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-018-9892-z", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3795456", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "63"
      }
    ], 
    "name": "On the Parameterized Complexity of Contraction to Generalization of Trees", 
    "pagination": "1-28", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "7af5f6aa036aa0fb70bfc5a83e772a61bd14f0418d616281736f3bea17d341f3"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-018-9892-z"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1109782415"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-018-9892-z", 
      "https://app.dimensions.ai/details/publication/pub.1109782415"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:54", 
    "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/0000000371_0000000371/records_130808_00000006.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00224-018-9892-z"
  }
]
 

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/s00224-018-9892-z'

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/s00224-018-9892-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-9892-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-9892-z'


 

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

161 TRIPLES      21 PREDICATES      52 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-018-9892-z schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N02e95860db0e467c95043c4b9b70992a
4 schema:citation sg:pub.10.1007/978-1-4471-5559-1
5 sg:pub.10.1007/978-3-319-03898-8_10
6 sg:pub.10.1007/978-3-319-03898-8_21
7 sg:pub.10.1007/978-3-319-21275-3
8 sg:pub.10.1007/978-3-319-57586-5_4
9 sg:pub.10.1007/978-3-642-31155-0_9
10 sg:pub.10.1007/s00236-014-0204-z
11 sg:pub.10.1007/s00453-012-9670-2
12 https://app.dimensions.ai/details/publication/pub.1004947649
13 https://app.dimensions.ai/details/publication/pub.1005955659
14 https://doi.org/10.1016/0020-0190(96)00050-6
15 https://doi.org/10.1016/0022-0000(83)90012-0
16 https://doi.org/10.1016/0166-218x(81)90039-1
17 https://doi.org/10.1016/0166-218x(83)90101-4
18 https://doi.org/10.1016/j.ipl.2013.09.004
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.tcs.2011.04.039
22 https://doi.org/10.1016/j.tcs.2012.12.041
23 https://doi.org/10.1016/j.tcs.2016.06.012
24 https://doi.org/10.1093/acprof:oso/9780198566076.001.0001
25 https://doi.org/10.1109/focs.2011.23
26 https://doi.org/10.1109/sfcs.1995.492475
27 https://doi.org/10.1137/130907392
28 https://doi.org/10.1145/3055399.3055456
29 schema:datePublished 2019-04
30 schema:datePublishedReg 2019-04-01
31 schema:description For a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S ⊆ E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al. [Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a “parameterized way”. Let Tℓ be the family of graphs such that each graph in Tℓ can be made into a tree by deleting at most ℓ edges. Thus, the problem we study is Tℓ-Contraction. We design an FPT algorithm for Tℓ-Contraction running in time O((2ℓ+2)O(k+ℓ)⋅nO(1)). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for Tℓ-Contraction of size O([k(k+2ℓ)](⌈αα−1⌉+1)).
32 schema:genre research_article
33 schema:inLanguage en
34 schema:isAccessibleForFree true
35 schema:isPartOf N94b464a418a14f42a03c07465b5566ba
36 Nc2a976b26feb4c2882bdeb05e42bb2db
37 sg:journal.1052098
38 schema:name On the Parameterized Complexity of Contraction to Generalization of Trees
39 schema:pagination 1-28
40 schema:productId N0fcf2575e33c45c78b2dbe85d2e8e540
41 N354428d1b06b404f97199a42c5c1b801
42 N87562662c0344cbea6807bee0bb2112c
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109782415
44 https://doi.org/10.1007/s00224-018-9892-z
45 schema:sdDatePublished 2019-04-11T13:54
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N87d05c27eaef42cf8bae7f71dd819815
48 schema:url https://link.springer.com/10.1007%2Fs00224-018-9892-z
49 sgo:license sg:explorer/license/
50 sgo:sdDataset articles
51 rdf:type schema:ScholarlyArticle
52 N02e95860db0e467c95043c4b9b70992a rdf:first N1114be75a45b440fa85fe66f048d9138
53 rdf:rest Nec0f5b0eb0934b70b2c7ee233caad75c
54 N0fcf2575e33c45c78b2dbe85d2e8e540 schema:name readcube_id
55 schema:value 7af5f6aa036aa0fb70bfc5a83e772a61bd14f0418d616281736f3bea17d341f3
56 rdf:type schema:PropertyValue
57 N1114be75a45b440fa85fe66f048d9138 schema:affiliation https://www.grid.ac/institutes/grid.7914.b
58 schema:familyName Agarwal
59 schema:givenName Akanksha
60 rdf:type schema:Person
61 N354428d1b06b404f97199a42c5c1b801 schema:name dimensions_id
62 schema:value pub.1109782415
63 rdf:type schema:PropertyValue
64 N777088b2c50b4245a51b465a1a501a53 rdf:first sg:person.011047776661.38
65 rdf:rest rdf:nil
66 N87562662c0344cbea6807bee0bb2112c schema:name doi
67 schema:value 10.1007/s00224-018-9892-z
68 rdf:type schema:PropertyValue
69 N87d05c27eaef42cf8bae7f71dd819815 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N94b464a418a14f42a03c07465b5566ba schema:issueNumber 3
72 rdf:type schema:PublicationIssue
73 Nc2a976b26feb4c2882bdeb05e42bb2db schema:volumeNumber 63
74 rdf:type schema:PublicationVolume
75 Nec0f5b0eb0934b70b2c7ee233caad75c rdf:first sg:person.014061711675.71
76 rdf:rest N777088b2c50b4245a51b465a1a501a53
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
81 schema:name Computation Theory and Mathematics
82 rdf:type schema:DefinedTerm
83 sg:grant.3795456 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-9892-z
84 rdf:type schema:MonetaryGrant
85 sg:journal.1052098 schema:issn 1432-4350
86 1433-0490
87 schema:name Theory of Computing Systems
88 rdf:type schema:Periodical
89 sg:person.011047776661.38 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
90 schema:familyName Tale
91 schema:givenName Prafullkumar
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011047776661.38
93 rdf:type schema:Person
94 sg:person.014061711675.71 schema:affiliation https://www.grid.ac/institutes/grid.462414.1
95 schema:familyName Saurabh
96 schema:givenName Saket
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014061711675.71
98 rdf:type schema:Person
99 sg:pub.10.1007/978-1-4471-5559-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005955659
100 https://doi.org/10.1007/978-1-4471-5559-1
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-3-319-03898-8_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007774141
103 https://doi.org/10.1007/978-3-319-03898-8_10
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/978-3-319-03898-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036594137
106 https://doi.org/10.1007/978-3-319-03898-8_21
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/978-3-319-21275-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004947649
109 https://doi.org/10.1007/978-3-319-21275-3
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-3-319-57586-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084851738
112 https://doi.org/10.1007/978-3-319-57586-5_4
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/978-3-642-31155-0_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009449672
115 https://doi.org/10.1007/978-3-642-31155-0_9
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/s00236-014-0204-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1020716903
118 https://doi.org/10.1007/s00236-014-0204-z
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/s00453-012-9670-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042020468
121 https://doi.org/10.1007/s00453-012-9670-2
122 rdf:type schema:CreativeWork
123 https://app.dimensions.ai/details/publication/pub.1004947649 schema:CreativeWork
124 https://app.dimensions.ai/details/publication/pub.1005955659 schema:CreativeWork
125 https://doi.org/10.1016/0020-0190(96)00050-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002138261
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1016/0022-0000(83)90012-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009598816
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1016/0166-218x(81)90039-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048629933
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1016/0166-218x(83)90101-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042950542
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1016/j.ipl.2013.09.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030715475
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1016/j.jcss.2009.04.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046558319
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1016/j.jcss.2010.06.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018586756
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1016/j.tcs.2011.04.039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006206581
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1016/j.tcs.2012.12.041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040706843
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1016/j.tcs.2016.06.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033495471
144 rdf:type schema:CreativeWork
145 https://doi.org/10.1093/acprof:oso/9780198566076.001.0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098761640
146 rdf:type schema:CreativeWork
147 https://doi.org/10.1109/focs.2011.23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095593381
148 rdf:type schema:CreativeWork
149 https://doi.org/10.1109/sfcs.1995.492475 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093736028
150 rdf:type schema:CreativeWork
151 https://doi.org/10.1137/130907392 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062870408
152 rdf:type schema:CreativeWork
153 https://doi.org/10.1145/3055399.3055456 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091880551
154 rdf:type schema:CreativeWork
155 https://www.grid.ac/institutes/grid.462414.1 schema:alternateName Institute of Mathematical Sciences
156 schema:name Department of Informatics, University of Bergen, Bergen, Norway
157 The Institute of Mathematical Sciences, HBNI, Chennai, India
158 rdf:type schema:Organization
159 https://www.grid.ac/institutes/grid.7914.b schema:alternateName University of Bergen
160 schema:name Department of Informatics, University of Bergen, Bergen, Norway
161 rdf:type schema:Organization
 




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


...