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": "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_381.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 Nc4d709016d264b0a9ae6e57341b1559a
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 N2ee85b36126e4aa5ac9a836c286861aa
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5cb90bd328554706a98f4bdbfb2bea87
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 N4d231e16dcef41e1ab02922015b08251
46 N87a1705632074d7cbd54e689a6262a9f
47 schema:publisher N6e93cb7002fe4a38976777eda031a798
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 2021-12-01T20:08
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher N478910413408469dbe8db7a19d83458d
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 N1e469063f1cb4774818cfff43bc0ece7 rdf:first N678235b1849e419b863c84f1c5a2aa2f
58 rdf:rest Ne3c5ba69bbf049b28036bbf6fc0613b8
59 N2ee85b36126e4aa5ac9a836c286861aa rdf:first Neaf9a0794db24dd0b28cf0341ecd2300
60 rdf:rest N1e469063f1cb4774818cfff43bc0ece7
61 N478910413408469dbe8db7a19d83458d schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N4d231e16dcef41e1ab02922015b08251 schema:name doi
64 schema:value 10.1007/3-540-56279-6_57
65 rdf:type schema:PropertyValue
66 N5cb90bd328554706a98f4bdbfb2bea87 schema:isbn 978-3-540-47501-9
67 978-3-540-56279-5
68 schema:name Algorithms and Computation
69 rdf:type schema:Book
70 N678235b1849e419b863c84f1c5a2aa2f schema:familyName Inagaki
71 schema:givenName Yasuyoshi
72 rdf:type schema:Person
73 N6e93cb7002fe4a38976777eda031a798 schema:name Springer Nature
74 rdf:type schema:Organisation
75 N795285d8f4a241468a76d2b3721210f1 rdf:first Nca0815aca45f4b4b801096633760f9b3
76 rdf:rest rdf:nil
77 N87a1705632074d7cbd54e689a6262a9f schema:name dimensions_id
78 schema:value pub.1013432288
79 rdf:type schema:PropertyValue
80 N915a432519144c8bac963213b5dc2462 rdf:first sg:person.07540250215.50
81 rdf:rest rdf:nil
82 N91ec7cd2cd1244b089ec2f351390db55 schema:familyName Iwama
83 schema:givenName Kazuo
84 rdf:type schema:Person
85 N96400dbad4a94387b941db0a4cb7c491 schema:familyName Nishizeki
86 schema:givenName Takao
87 rdf:type schema:Person
88 Nc4d709016d264b0a9ae6e57341b1559a rdf:first sg:person.014072526441.41
89 rdf:rest N915a432519144c8bac963213b5dc2462
90 Nca0815aca45f4b4b801096633760f9b3 schema:familyName Yamashita
91 schema:givenName Masafumi
92 rdf:type schema:Person
93 Ne3c5ba69bbf049b28036bbf6fc0613b8 rdf:first N91ec7cd2cd1244b089ec2f351390db55
94 rdf:rest Nf31bf804fb314a58bebd7d53e1bc49e3
95 Neaf9a0794db24dd0b28cf0341ecd2300 schema:familyName Ibaraki
96 schema:givenName Toshihide
97 rdf:type schema:Person
98 Nf31bf804fb314a58bebd7d53e1bc49e3 rdf:first N96400dbad4a94387b941db0a4cb7c491
99 rdf:rest N795285d8f4a241468a76d2b3721210f1
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)


...