{
"@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"
}