The application of the searching over separators strategy to solve some NP-complete problems on planar graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1992

AUTHORS

R. Z. Hwang , R. C. T. Lee

ABSTRACT

Recently, we proposed a new strategy for designing algorithms, called the searching over separators strategy. We applied this approach to solve some famous NP-Complete problems in subexponential time such as the discrete Euclidean P-median problem, the discrete Euclidean P-center problem, the Euclidean P-center problem and the Euclidean traveling salesperson problem. In this paper, we further extend this strategy to solve two well known NP-Complete problems, the planar partition-into-clique problem (PCliPar) and the planar steiner tree problem (PStTree). We propose \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(n^{o(\sqrt n )} )$$ \end{document} algorithms for both problems, where n is the number of vertices in the input graph. More... »

PAGES

51-60

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-56279-6_57

DOI

http://dx.doi.org/10.1007/3-540-56279-6_57

DIMENSIONS

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


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": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, 30043, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, 30043, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hwang", 
        "givenName": "R. Z.", 
        "id": "sg:person.014072526441.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014072526441.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, 30043, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, 30043, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "R. C. T.", 
        "id": "sg:person.07540250215.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "Recently, we proposed a new strategy for designing algorithms, called the searching over separators strategy. We applied this approach to solve some famous NP-Complete problems in subexponential time such as the discrete Euclidean P-median problem, the discrete Euclidean P-center problem, the Euclidean P-center problem and the Euclidean traveling salesperson problem. In this paper, we further extend this strategy to solve two well known NP-Complete problems, the planar partition-into-clique problem (PCliPar) and the planar steiner tree problem (PStTree). We propose \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$O(n^{o(\\sqrt n )} )$$\n\\end{document} algorithms for both problems, where n is the number of vertices in the input graph.", 
    "editor": [
      {
        "familyName": "Ibaraki", 
        "givenName": "Toshihide", 
        "type": "Person"
      }, 
      {
        "familyName": "Inagaki", 
        "givenName": "Yasuyoshi", 
        "type": "Person"
      }, 
      {
        "familyName": "Iwama", 
        "givenName": "Kazuo", 
        "type": "Person"
      }, 
      {
        "familyName": "Nishizeki", 
        "givenName": "Takao", 
        "type": "Person"
      }, 
      {
        "familyName": "Yamashita", 
        "givenName": "Masafumi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-56279-6_57", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-56279-5", 
        "978-3-540-47501-9"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "NP-complete problem", 
      "famous NP-complete problem", 
      "center problem", 
      "Steiner tree problem", 
      "Euclidean p", 
      "input graph", 
      "clique problem", 
      "salesperson problem", 
      "subexponential time", 
      "median problem", 
      "number of vertices", 
      "tree problem", 
      "searching", 
      "planar partition", 
      "graph", 
      "planar graphs", 
      "algorithm", 
      "partition", 
      "Euclidean", 
      "applications", 
      "vertices", 
      "strategies", 
      "new strategy", 
      "number", 
      "time", 
      "problem", 
      "paper", 
      "approach", 
      "separators strategy", 
      "discrete Euclidean P", 
      "planar steiner tree problem"
    ], 
    "name": "The application of the searching over separators strategy to solve some NP-complete problems on planar graphs", 
    "pagination": "51-60", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013432288"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-56279-6_57"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-56279-6_57", 
      "https://app.dimensions.ai/details/publication/pub.1013432288"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_217.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-56279-6_57"
  }
]
 

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/3-540-56279-6_57'

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/3-540-56279-6_57'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-56279-6_57'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-56279-6_57'


 

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

118 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-56279-6_57 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb0061ddea4224bfe86cef536ac86c918
4 schema:datePublished 1992
5 schema:datePublishedReg 1992-01-01
6 schema:description Recently, we proposed a new strategy for designing algorithms, called the searching over separators strategy. We applied this approach to solve some famous NP-Complete problems in subexponential time such as the discrete Euclidean P-median problem, the discrete Euclidean P-center problem, the Euclidean P-center problem and the Euclidean traveling salesperson problem. In this paper, we further extend this strategy to solve two well known NP-Complete problems, the planar partition-into-clique problem (PCliPar) and the planar steiner tree problem (PStTree). We propose \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(n^{o(\sqrt n )} )$$ \end{document} algorithms for both problems, where n is the number of vertices in the input graph.
7 schema:editor N815338149b4643f3895bd2c733d155ea
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nccf351694c4a4c9a898c425cd3a24cf3
12 schema:keywords Euclidean
13 Euclidean p
14 NP-complete problem
15 Steiner tree problem
16 algorithm
17 applications
18 approach
19 center problem
20 clique problem
21 discrete Euclidean P
22 famous NP-complete problem
23 graph
24 input graph
25 median problem
26 new strategy
27 number
28 number of vertices
29 paper
30 partition
31 planar graphs
32 planar partition
33 planar steiner tree problem
34 problem
35 salesperson problem
36 searching
37 separators strategy
38 strategies
39 subexponential time
40 time
41 tree problem
42 vertices
43 schema:name The application of the searching over separators strategy to solve some NP-complete problems on planar graphs
44 schema:pagination 51-60
45 schema:productId N04af6016d75d4747b65214f17bfeac15
46 N1312f1e9548c4018b047ccf153366f25
47 schema:publisher N39449690ac144b1eb4e5efa4fc63bdcf
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013432288
49 https://doi.org/10.1007/3-540-56279-6_57
50 schema:sdDatePublished 2022-01-01T19:12
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher N0834bd18b7ec48a08abec17eb080d16b
53 schema:url https://doi.org/10.1007/3-540-56279-6_57
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N04af6016d75d4747b65214f17bfeac15 schema:name dimensions_id
58 schema:value pub.1013432288
59 rdf:type schema:PropertyValue
60 N0834bd18b7ec48a08abec17eb080d16b schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N0ccb0d0e619e43708048476241218ad7 rdf:first Neebebde04cba42a8b7c18be7736ee458
63 rdf:rest N16df968a6ac24573a51bc3bebb27a722
64 N1312f1e9548c4018b047ccf153366f25 schema:name doi
65 schema:value 10.1007/3-540-56279-6_57
66 rdf:type schema:PropertyValue
67 N16df968a6ac24573a51bc3bebb27a722 rdf:first N48d1a81b3727412286766ff076609886
68 rdf:rest rdf:nil
69 N39449690ac144b1eb4e5efa4fc63bdcf schema:name Springer Nature
70 rdf:type schema:Organisation
71 N3a4125d434bb455aab6737dfd9217fea schema:familyName Ibaraki
72 schema:givenName Toshihide
73 rdf:type schema:Person
74 N41c66fe84c744fdd88356ebd0cb8177b schema:familyName Iwama
75 schema:givenName Kazuo
76 rdf:type schema:Person
77 N48d1a81b3727412286766ff076609886 schema:familyName Yamashita
78 schema:givenName Masafumi
79 rdf:type schema:Person
80 N4f070e3a70a249969b9ea5d5bb1b0f55 rdf:first N41c66fe84c744fdd88356ebd0cb8177b
81 rdf:rest N0ccb0d0e619e43708048476241218ad7
82 N5beee2eb9ad44892829d015d44b03f13 rdf:first sg:person.07540250215.50
83 rdf:rest rdf:nil
84 N815338149b4643f3895bd2c733d155ea rdf:first N3a4125d434bb455aab6737dfd9217fea
85 rdf:rest N91d2fc2ae60b4ab5a6b083a14555ccd1
86 N91d2fc2ae60b4ab5a6b083a14555ccd1 rdf:first Nee06e3787c4c47b8a3e99796eea7aaec
87 rdf:rest N4f070e3a70a249969b9ea5d5bb1b0f55
88 Nb0061ddea4224bfe86cef536ac86c918 rdf:first sg:person.014072526441.41
89 rdf:rest N5beee2eb9ad44892829d015d44b03f13
90 Nccf351694c4a4c9a898c425cd3a24cf3 schema:isbn 978-3-540-47501-9
91 978-3-540-56279-5
92 schema:name Algorithms and Computation
93 rdf:type schema:Book
94 Nee06e3787c4c47b8a3e99796eea7aaec schema:familyName Inagaki
95 schema:givenName Yasuyoshi
96 rdf:type schema:Person
97 Neebebde04cba42a8b7c18be7736ee458 schema:familyName Nishizeki
98 schema:givenName Takao
99 rdf:type schema:Person
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
104 schema:name Computation Theory and Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.014072526441.41 schema:affiliation grid-institutes:grid.38348.34
107 schema:familyName Hwang
108 schema:givenName R. Z.
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014072526441.41
110 rdf:type schema:Person
111 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.38348.34
112 schema:familyName Lee
113 schema:givenName R. C. T.
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
115 rdf:type schema:Person
116 grid-institutes:grid.38348.34 schema:alternateName Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, 30043, Republic of China
117 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, 30043, Republic of China
118 rdf:type schema:Organization
 




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


...