On Conditional Covering Problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-03

AUTHORS

Balasubramanian Sivan, S. Harini, C. Pandu Rangan

ABSTRACT

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n3) algorithm for the same. We also propose an O(n2) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity. More... »

PAGES

97-107

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s11786-009-0001-1

DOI

http://dx.doi.org/10.1007/s11786-009-0001-1

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": {
          "alternateName": "University of Wisconsin\u2013Madison", 
          "id": "https://www.grid.ac/institutes/grid.14003.36", 
          "name": [
            "Computer Sciences Department, University of Wisconsin Madison, 53706, Madison, WI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sivan", 
        "givenName": "Balasubramanian", 
        "id": "sg:person.012400307453.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012400307453.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Madras", 
          "id": "https://www.grid.ac/institutes/grid.417969.4", 
          "name": [
            "Department of Computer Science and Engineering, Indian Institute of Technology Madras, 600036, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Harini", 
        "givenName": "S.", 
        "id": "sg:person.016133035127.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016133035127.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Madras", 
          "id": "https://www.grid.ac/institutes/grid.417969.4", 
          "name": [
            "Department of Computer Science and Engineering, Indian Institute of Technology Madras, 600036, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pandu Rangan", 
        "givenName": "C.", 
        "id": "sg:person.016366027737.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0166-218x(99)00128-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026781925"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.20087", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033057474"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.20087", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033057474"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/nav.20074", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042973410"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.20086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043087032"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.20086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043087032"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0305-0548(94)00079-n", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044061217"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0305-0548(87)90053-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049246559"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0305-0548(87)90053-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049246559"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.30.3.290", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064719865"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-03", 
    "datePublishedReg": "2010-03-01", 
    "description": "The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177\u2013185, 2005). We show that their algorithm is wrong and further present a correct O(n3) algorithm for the same. We also propose an O(n2) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s11786-009-0001-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136594", 
        "issn": [
          "1661-8270", 
          "1661-8289"
        ], 
        "name": "Mathematics in Computer Science", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "3"
      }
    ], 
    "name": "On Conditional Covering Problem", 
    "pagination": "97-107", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "295c3ce1ab4f0ee381bd70d05942477ce547effd0caddcf17122f328c7dc17b2"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s11786-009-0001-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008681399"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s11786-009-0001-1", 
      "https://app.dimensions.ai/details/publication/pub.1008681399"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T21:38", 
    "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_8687_00000520.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs11786-009-0001-1"
  }
]
 

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/s11786-009-0001-1'

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/s11786-009-0001-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11786-009-0001-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11786-009-0001-1'


 

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

99 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s11786-009-0001-1 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nea470c1541dd4f21b3ba500dda5bf419
4 schema:citation https://doi.org/10.1002/nav.20074
5 https://doi.org/10.1002/net.20086
6 https://doi.org/10.1002/net.20087
7 https://doi.org/10.1016/0305-0548(87)90053-0
8 https://doi.org/10.1016/0305-0548(94)00079-n
9 https://doi.org/10.1016/s0166-218x(99)00128-6
10 https://doi.org/10.1287/mnsc.30.3.290
11 schema:datePublished 2010-03
12 schema:datePublishedReg 2010-03-01
13 schema:description The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n3) algorithm for the same. We also propose an O(n2) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.
14 schema:genre research_article
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N4e73085cba854155b4dd6051a8649843
18 Nd3251bc9fa3441948fbd0bbffb09dd7b
19 sg:journal.1136594
20 schema:name On Conditional Covering Problem
21 schema:pagination 97-107
22 schema:productId N6b3eb50fcc734f94be9d3ed3bd00be1c
23 N7f18e0f0cfcf4985bd990108f3501ffb
24 Na3d7daa9872146398a9d6e6d567fb21b
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008681399
26 https://doi.org/10.1007/s11786-009-0001-1
27 schema:sdDatePublished 2019-04-10T21:38
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher N3a252fb38c674ade996869919f2b7fd6
30 schema:url http://link.springer.com/10.1007%2Fs11786-009-0001-1
31 sgo:license sg:explorer/license/
32 sgo:sdDataset articles
33 rdf:type schema:ScholarlyArticle
34 N3a252fb38c674ade996869919f2b7fd6 schema:name Springer Nature - SN SciGraph project
35 rdf:type schema:Organization
36 N494cc3bae74447d0968431e5e46d9737 rdf:first sg:person.016366027737.61
37 rdf:rest rdf:nil
38 N4e73085cba854155b4dd6051a8649843 schema:issueNumber 1
39 rdf:type schema:PublicationIssue
40 N6b3eb50fcc734f94be9d3ed3bd00be1c schema:name doi
41 schema:value 10.1007/s11786-009-0001-1
42 rdf:type schema:PropertyValue
43 N7f18e0f0cfcf4985bd990108f3501ffb schema:name dimensions_id
44 schema:value pub.1008681399
45 rdf:type schema:PropertyValue
46 Na3d7daa9872146398a9d6e6d567fb21b schema:name readcube_id
47 schema:value 295c3ce1ab4f0ee381bd70d05942477ce547effd0caddcf17122f328c7dc17b2
48 rdf:type schema:PropertyValue
49 Na883b7105559424ab9b2966ed0304471 rdf:first sg:person.016133035127.62
50 rdf:rest N494cc3bae74447d0968431e5e46d9737
51 Nd3251bc9fa3441948fbd0bbffb09dd7b schema:volumeNumber 3
52 rdf:type schema:PublicationVolume
53 Nea470c1541dd4f21b3ba500dda5bf419 rdf:first sg:person.012400307453.12
54 rdf:rest Na883b7105559424ab9b2966ed0304471
55 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
56 schema:name Information and Computing Sciences
57 rdf:type schema:DefinedTerm
58 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
59 schema:name Artificial Intelligence and Image Processing
60 rdf:type schema:DefinedTerm
61 sg:journal.1136594 schema:issn 1661-8270
62 1661-8289
63 schema:name Mathematics in Computer Science
64 rdf:type schema:Periodical
65 sg:person.012400307453.12 schema:affiliation https://www.grid.ac/institutes/grid.14003.36
66 schema:familyName Sivan
67 schema:givenName Balasubramanian
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012400307453.12
69 rdf:type schema:Person
70 sg:person.016133035127.62 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
71 schema:familyName Harini
72 schema:givenName S.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016133035127.62
74 rdf:type schema:Person
75 sg:person.016366027737.61 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
76 schema:familyName Pandu Rangan
77 schema:givenName C.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61
79 rdf:type schema:Person
80 https://doi.org/10.1002/nav.20074 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042973410
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1002/net.20086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043087032
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1002/net.20087 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033057474
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1016/0305-0548(87)90053-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049246559
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1016/0305-0548(94)00079-n schema:sameAs https://app.dimensions.ai/details/publication/pub.1044061217
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/s0166-218x(99)00128-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026781925
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1287/mnsc.30.3.290 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064719865
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.14003.36 schema:alternateName University of Wisconsin–Madison
95 schema:name Computer Sciences Department, University of Wisconsin Madison, 53706, Madison, WI, USA
96 rdf:type schema:Organization
97 https://www.grid.ac/institutes/grid.417969.4 schema:alternateName Indian Institute of Technology Madras
98 schema:name Department of Computer Science and Engineering, Indian Institute of Technology Madras, 600036, Chennai, India
99 rdf:type schema:Organization
 




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


...