An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1999-02

AUTHORS

William C.K. Yen, C.Y. Tang

ABSTRACT

In this paper, we consider a graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Our problem is an extension of so-called graph searching/guarding problem by considering the time slot parameter in addition to the traditional building cost. Suppose that there is a fugitive who moves along the edges of the graph at any speed. We want to place a set of searchlights at the vertices to search the edges of the graph and capture the fugitive. It costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total costs of the vertices in S is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, the time slots needed to capture the fugitive is the minimum. The problem is known to be NP-hard on weighted bipartite graphs, split graphs, and chordal graphs; and it is linear time solvable on weighted trees and interval graphs. In this paper, an algorithm is designed to solve the problem on weighted two-terminal series-parallel graphs. It works on the parsing tree structure of the given two-terminal series-parallel graph. The algorithm is divided into two phases. In the phase one, we first extract some useful properties of optimal solutions. Employing these properties, an algorithm is designed to find the set of searchlights with the minimum guarding cost and to assign the searching directions of all edges by the dynamic programming strategy. In the phase two, the searched time slots of all edges are determined by the breadth-first-search from the root of the parsing tree. The time complexities of both phases are linear. Thus, our algorithm is time optimal. More... »

PAGES

143-172

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s002360050156

DOI

http://dx.doi.org/10.1007/s002360050156

DIMENSIONS

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


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": {
          "name": [
            "Department of Business Administration, Ming-Hsin Institute of Technology, Hsin-Feng, Hsinchu 304, Taiwan, R.O.C. (e-mail: ckyen001@ms7.hinet.net), TW"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yen", 
        "givenName": "William C.K.", 
        "id": "sg:person.015533475461.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015533475461.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, R.O.C. (e-mail: cytang@cs.nthu.edu.tw), TW"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "C.Y.", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999-02", 
    "datePublishedReg": "1999-02-01", 
    "description": "In this paper, we consider a graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Our problem is an extension of so-called graph searching/guarding problem by considering the time slot parameter in addition to the traditional building cost. Suppose that there is a fugitive who moves along the edges of the graph at any speed. We want to place a set of searchlights at the vertices to search the edges of the graph and capture the fugitive. It costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total costs of the vertices in S is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, the time slots needed to capture the fugitive is the minimum. The problem is known to be NP-hard on weighted bipartite graphs, split graphs, and chordal graphs; and it is linear time solvable on weighted trees and interval graphs. In this paper, an algorithm is designed to solve the problem on weighted two-terminal series-parallel graphs. It works on the parsing tree structure of the given two-terminal series-parallel graph. The algorithm is divided into two phases. In the phase one, we first extract some useful properties of optimal solutions. Employing these properties, an algorithm is designed to find the set of searchlights with the minimum guarding cost and to assign the searching directions of all edges by the dynamic programming strategy. In the phase two, the searched time slots of all edges are determined by the breadth-first-search from the root of the parsing tree. The time complexities of both phases are linear. Thus, our algorithm is time optimal.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s002360050156", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1133515", 
        "issn": [
          "0001-5903", 
          "1432-0525"
        ], 
        "name": "Acta Informatica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "36"
      }
    ], 
    "name": "An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs", 
    "pagination": "143-172", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d374d9160f2d6fd76d7e57de79409b6fa24d202345dde02f109ada4ee562dbdc"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s002360050156"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044392044"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s002360050156", 
      "https://app.dimensions.ai/details/publication/pub.1044392044"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T01:52", 
    "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/0000000001_0000000264/records_8700_00000482.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s002360050156"
  }
]
 

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/s002360050156'

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/s002360050156'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s002360050156'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s002360050156'


 

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

70 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s002360050156 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb4e871ef154d4c0fb1c7ee14fd429ee9
4 schema:datePublished 1999-02
5 schema:datePublishedReg 1999-02-01
6 schema:description In this paper, we consider a graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Our problem is an extension of so-called graph searching/guarding problem by considering the time slot parameter in addition to the traditional building cost. Suppose that there is a fugitive who moves along the edges of the graph at any speed. We want to place a set of searchlights at the vertices to search the edges of the graph and capture the fugitive. It costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total costs of the vertices in S is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, the time slots needed to capture the fugitive is the minimum. The problem is known to be NP-hard on weighted bipartite graphs, split graphs, and chordal graphs; and it is linear time solvable on weighted trees and interval graphs. In this paper, an algorithm is designed to solve the problem on weighted two-terminal series-parallel graphs. It works on the parsing tree structure of the given two-terminal series-parallel graph. The algorithm is divided into two phases. In the phase one, we first extract some useful properties of optimal solutions. Employing these properties, an algorithm is designed to find the set of searchlights with the minimum guarding cost and to assign the searching directions of all edges by the dynamic programming strategy. In the phase two, the searched time slots of all edges are determined by the breadth-first-search from the root of the parsing tree. The time complexities of both phases are linear. Thus, our algorithm is time optimal.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf Na01ae9d7a786425d8a744ca06967211c
11 Nf88d8422d6624037a0f500669fe5a7ab
12 sg:journal.1133515
13 schema:name An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs
14 schema:pagination 143-172
15 schema:productId N79b385b8a6f142b1be369917152a8122
16 Nd3b0754f396d43239cb7b7f2a1663cad
17 Nf3775faf46b842ef925edc43b39f44ef
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044392044
19 https://doi.org/10.1007/s002360050156
20 schema:sdDatePublished 2019-04-11T01:52
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nc642f6f74c46441d94bf8c8d1498d831
23 schema:url http://link.springer.com/10.1007/s002360050156
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N79b385b8a6f142b1be369917152a8122 schema:name dimensions_id
28 schema:value pub.1044392044
29 rdf:type schema:PropertyValue
30 Na01ae9d7a786425d8a744ca06967211c schema:volumeNumber 36
31 rdf:type schema:PublicationVolume
32 Na4bc70b16e774397af9975b17ac08a3c rdf:first sg:person.01312526135.27
33 rdf:rest rdf:nil
34 Naee0d570ec6a43f9b28a49d83ea62c89 schema:name Department of Business Administration, Ming-Hsin Institute of Technology, Hsin-Feng, Hsinchu 304, Taiwan, R.O.C. (e-mail: ckyen001@ms7.hinet.net), TW
35 rdf:type schema:Organization
36 Nb4e871ef154d4c0fb1c7ee14fd429ee9 rdf:first sg:person.015533475461.43
37 rdf:rest Na4bc70b16e774397af9975b17ac08a3c
38 Nc642f6f74c46441d94bf8c8d1498d831 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 Nd3b0754f396d43239cb7b7f2a1663cad schema:name doi
41 schema:value 10.1007/s002360050156
42 rdf:type schema:PropertyValue
43 Nf3775faf46b842ef925edc43b39f44ef schema:name readcube_id
44 schema:value d374d9160f2d6fd76d7e57de79409b6fa24d202345dde02f109ada4ee562dbdc
45 rdf:type schema:PropertyValue
46 Nf88d8422d6624037a0f500669fe5a7ab schema:issueNumber 2
47 rdf:type schema:PublicationIssue
48 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
49 schema:name Information and Computing Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
52 schema:name Computation Theory and Mathematics
53 rdf:type schema:DefinedTerm
54 sg:journal.1133515 schema:issn 0001-5903
55 1432-0525
56 schema:name Acta Informatica
57 rdf:type schema:Periodical
58 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
59 schema:familyName Tang
60 schema:givenName C.Y.
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
62 rdf:type schema:Person
63 sg:person.015533475461.43 schema:affiliation Naee0d570ec6a43f9b28a49d83ea62c89
64 schema:familyName Yen
65 schema:givenName William C.K.
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015533475461.43
67 rdf:type schema:Person
68 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
69 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, R.O.C. (e-mail: cytang@cs.nthu.edu.tw), TW
70 rdf:type schema:Organization
 




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


...