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 Ne79c4e4c83264965abb5c00210929c44
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 N0c2cee39966740a291ccf33dee2f73d0
11 N9d86f972bd314dec9ce30c1756893114
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 Nab0f4056b24d4f9aaca03bedd8b4f2ee
16 Nd519fb070cc147b79e3d70acfae9920d
17 Nef570c63a275437db7184526e2ad5df6
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 N15d6089fea304e8fb6e025963ef94a43
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 N0c2cee39966740a291ccf33dee2f73d0 schema:volumeNumber 36
28 rdf:type schema:PublicationVolume
29 N15d6089fea304e8fb6e025963ef94a43 schema:name Springer Nature - SN SciGraph project
30 rdf:type schema:Organization
31 N9d86f972bd314dec9ce30c1756893114 schema:issueNumber 2
32 rdf:type schema:PublicationIssue
33 Nab0f4056b24d4f9aaca03bedd8b4f2ee schema:name dimensions_id
34 schema:value pub.1044392044
35 rdf:type schema:PropertyValue
36 Nc3be91809e4f44d8928e4cb4d3867ded 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
37 rdf:type schema:Organization
38 Nc6c16f9d08cb41b4873c58b3203ae25a rdf:first sg:person.01312526135.27
39 rdf:rest rdf:nil
40 Nd519fb070cc147b79e3d70acfae9920d schema:name readcube_id
41 schema:value d374d9160f2d6fd76d7e57de79409b6fa24d202345dde02f109ada4ee562dbdc
42 rdf:type schema:PropertyValue
43 Ne79c4e4c83264965abb5c00210929c44 rdf:first sg:person.015533475461.43
44 rdf:rest Nc6c16f9d08cb41b4873c58b3203ae25a
45 Nef570c63a275437db7184526e2ad5df6 schema:name doi
46 schema:value 10.1007/s002360050156
47 rdf:type schema:PropertyValue
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 Nc3be91809e4f44d8928e4cb4d3867ded
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)


...