On the Complexity of Reconfiguration Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Takehiro Ito , Erik D. Demaine , Nicholas J. A. Harvey , Christos H. Papadimitriou , Martha Sideri , Ryuhei Uehara , Yushi Uno

ABSTRACT

Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. More... »

PAGES

28-39

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-92182-0_6

DOI

http://dx.doi.org/10.1007/978-3-540-92182-0_6

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, 980-8579, Sendai, Japan", 
          "id": "http://www.grid.ac/institutes/grid.69566.3a", 
          "name": [
            "Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, 980-8579, Sendai, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ito", 
        "givenName": "Takehiro", 
        "id": "sg:person.010153545271.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010153545271.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., MA 02139, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., MA 02139, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Demaine", 
        "givenName": "Erik D.", 
        "id": "sg:person.015206033153.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015206033153.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., MA 02139, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., MA 02139, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Harvey", 
        "givenName": "Nicholas J. A.", 
        "id": "sg:person.014213777677.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213777677.09"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California at Berkeley, Soda Hall 689, EECS Department, CA 94720, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California at Berkeley, Soda Hall 689, EECS Department, CA 94720, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Athens University of Economics and Business, Patision 76, 10434, Athens, Greece", 
          "id": "http://www.grid.ac/institutes/grid.16299.35", 
          "name": [
            "Department of Computer Science, Athens University of Economics and Business, Patision 76, 10434, Athens, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sideri", 
        "givenName": "Martha", 
        "id": "sg:person.016347202663.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347202663.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Information Science, JAIST, Asahidai 1-1, Nomi, 923-1292, Ishikawa, Japan", 
          "id": "http://www.grid.ac/institutes/grid.444515.5", 
          "name": [
            "School of Information Science, JAIST, Asahidai 1-1, Nomi, 923-1292, Ishikawa, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uehara", 
        "givenName": "Ryuhei", 
        "id": "sg:person.011467765731.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011467765731.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graduate School of Science, Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, 599-8531, Sakai, Japan", 
          "id": "http://www.grid.ac/institutes/grid.261455.1", 
          "name": [
            "Graduate School of Science, Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, 599-8531, Sakai, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uno", 
        "givenName": "Yushi", 
        "id": "sg:person.016070367373.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016070367373.00"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.", 
    "editor": [
      {
        "familyName": "Hong", 
        "givenName": "Seok-Hee", 
        "type": "Person"
      }, 
      {
        "familyName": "Nagamochi", 
        "givenName": "Hiroshi", 
        "type": "Person"
      }, 
      {
        "familyName": "Fukunaga", 
        "givenName": "Takuro", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-92182-0_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-92181-3", 
        "978-3-540-92182-0"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "reconfiguration problem", 
      "NP-complete problem", 
      "polynomial time", 
      "reconfiguration versions", 
      "feasible solution", 
      "intermediate results", 
      "complexity", 
      "NP", 
      "version", 
      "solution", 
      "step", 
      "step transformation", 
      "time", 
      "transformation", 
      "results", 
      "host", 
      "contrast", 
      "problem"
    ], 
    "name": "On the Complexity of Reconfiguration Problems", 
    "pagination": "28-39", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014936060"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-92182-0_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-92182-0_6", 
      "https://app.dimensions.ai/details/publication/pub.1014936060"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:08", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_39.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-92182-0_6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92182-0_6'

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-540-92182-0_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-92182-0_6'

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-540-92182-0_6'


 

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

145 TRIPLES      23 PREDICATES      44 URIs      37 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-92182-0_6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2f4a8fb5ee4940e38b316d1629ccca49
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema:description Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.
7 schema:editor N205bf76376564192ac237a232d18ecb4
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na13afe0de0d840189e33281b5654bc6d
12 schema:keywords NP
13 NP-complete problem
14 complexity
15 contrast
16 feasible solution
17 host
18 intermediate results
19 polynomial time
20 problem
21 reconfiguration problem
22 reconfiguration versions
23 results
24 solution
25 step
26 step transformation
27 time
28 transformation
29 version
30 schema:name On the Complexity of Reconfiguration Problems
31 schema:pagination 28-39
32 schema:productId N1867f369234e40b98bca770fa4b3e8b7
33 N51bdbd2b53e748eea60e276acf480f7f
34 schema:publisher Nb3e3eb2bdb424f3bb88112a9f7eb1ac4
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014936060
36 https://doi.org/10.1007/978-3-540-92182-0_6
37 schema:sdDatePublished 2021-12-01T20:08
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N380a5eb3ee2e4bd2ac4c9fc19de038e1
40 schema:url https://doi.org/10.1007/978-3-540-92182-0_6
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N07b13ccdd9bb4ea6a670efdc9ff1ccc7 rdf:first Nac42cfc1a90e450896760df12be3b99d
45 rdf:rest rdf:nil
46 N1867f369234e40b98bca770fa4b3e8b7 schema:name dimensions_id
47 schema:value pub.1014936060
48 rdf:type schema:PropertyValue
49 N205bf76376564192ac237a232d18ecb4 rdf:first Ndb618be68938499081d76db2aa2a0327
50 rdf:rest Naf207638f2ea475b99357d4eb4749d98
51 N2f4a8fb5ee4940e38b316d1629ccca49 rdf:first sg:person.010153545271.39
52 rdf:rest Nca53c17625754a989bf54ea452688f80
53 N380a5eb3ee2e4bd2ac4c9fc19de038e1 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 N51bdbd2b53e748eea60e276acf480f7f schema:name doi
56 schema:value 10.1007/978-3-540-92182-0_6
57 rdf:type schema:PropertyValue
58 N522bcdcf30c74720a3d6ca4c2fa184da schema:familyName Nagamochi
59 schema:givenName Hiroshi
60 rdf:type schema:Person
61 N8f08e105d20741dcb7f31d5f63e5c525 rdf:first sg:person.011467765731.43
62 rdf:rest Nd01b23ad19a64b3695d3663eefc18b6c
63 Na13afe0de0d840189e33281b5654bc6d schema:isbn 978-3-540-92181-3
64 978-3-540-92182-0
65 schema:name Algorithms and Computation
66 rdf:type schema:Book
67 Nac42cfc1a90e450896760df12be3b99d schema:familyName Fukunaga
68 schema:givenName Takuro
69 rdf:type schema:Person
70 Naf207638f2ea475b99357d4eb4749d98 rdf:first N522bcdcf30c74720a3d6ca4c2fa184da
71 rdf:rest N07b13ccdd9bb4ea6a670efdc9ff1ccc7
72 Nb3e3eb2bdb424f3bb88112a9f7eb1ac4 schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nbb04c781367747058d66295245444f8d rdf:first sg:person.014213777677.09
75 rdf:rest Ncf01b08fd26d496697834d718ed5eff9
76 Nca53c17625754a989bf54ea452688f80 rdf:first sg:person.015206033153.81
77 rdf:rest Nbb04c781367747058d66295245444f8d
78 Ncf01b08fd26d496697834d718ed5eff9 rdf:first sg:person.013233165465.63
79 rdf:rest Nffd8cad9b5ae4eb8a0238c95df31935e
80 Nd01b23ad19a64b3695d3663eefc18b6c rdf:first sg:person.016070367373.00
81 rdf:rest rdf:nil
82 Ndb618be68938499081d76db2aa2a0327 schema:familyName Hong
83 schema:givenName Seok-Hee
84 rdf:type schema:Person
85 Nffd8cad9b5ae4eb8a0238c95df31935e rdf:first sg:person.016347202663.46
86 rdf:rest N8f08e105d20741dcb7f31d5f63e5c525
87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
88 schema:name Information and Computing Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
91 schema:name Computation Theory and Mathematics
92 rdf:type schema:DefinedTerm
93 sg:person.010153545271.39 schema:affiliation grid-institutes:grid.69566.3a
94 schema:familyName Ito
95 schema:givenName Takehiro
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010153545271.39
97 rdf:type schema:Person
98 sg:person.011467765731.43 schema:affiliation grid-institutes:grid.444515.5
99 schema:familyName Uehara
100 schema:givenName Ryuhei
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011467765731.43
102 rdf:type schema:Person
103 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
104 schema:familyName Papadimitriou
105 schema:givenName Christos H.
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
107 rdf:type schema:Person
108 sg:person.014213777677.09 schema:affiliation grid-institutes:grid.116068.8
109 schema:familyName Harvey
110 schema:givenName Nicholas J. A.
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213777677.09
112 rdf:type schema:Person
113 sg:person.015206033153.81 schema:affiliation grid-institutes:grid.116068.8
114 schema:familyName Demaine
115 schema:givenName Erik D.
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015206033153.81
117 rdf:type schema:Person
118 sg:person.016070367373.00 schema:affiliation grid-institutes:grid.261455.1
119 schema:familyName Uno
120 schema:givenName Yushi
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016070367373.00
122 rdf:type schema:Person
123 sg:person.016347202663.46 schema:affiliation grid-institutes:grid.16299.35
124 schema:familyName Sideri
125 schema:givenName Martha
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347202663.46
127 rdf:type schema:Person
128 grid-institutes:grid.116068.8 schema:alternateName MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., MA 02139, Cambridge, USA
129 schema:name MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., MA 02139, Cambridge, USA
130 rdf:type schema:Organization
131 grid-institutes:grid.16299.35 schema:alternateName Department of Computer Science, Athens University of Economics and Business, Patision 76, 10434, Athens, Greece
132 schema:name Department of Computer Science, Athens University of Economics and Business, Patision 76, 10434, Athens, Greece
133 rdf:type schema:Organization
134 grid-institutes:grid.261455.1 schema:alternateName Graduate School of Science, Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, 599-8531, Sakai, Japan
135 schema:name Graduate School of Science, Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, 599-8531, Sakai, Japan
136 rdf:type schema:Organization
137 grid-institutes:grid.444515.5 schema:alternateName School of Information Science, JAIST, Asahidai 1-1, Nomi, 923-1292, Ishikawa, Japan
138 schema:name School of Information Science, JAIST, Asahidai 1-1, Nomi, 923-1292, Ishikawa, Japan
139 rdf:type schema:Organization
140 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California at Berkeley, Soda Hall 689, EECS Department, CA 94720, Berkeley, USA
141 schema:name Computer Science Division, University of California at Berkeley, Soda Hall 689, EECS Department, CA 94720, Berkeley, USA
142 rdf:type schema:Organization
143 grid-institutes:grid.69566.3a schema:alternateName Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, 980-8579, Sendai, Japan
144 schema:name Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, 980-8579, Sendai, Japan
145 rdf:type schema:Organization
 




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


...