Weighted domination on cocomparability graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Maw-Shang Chang

ABSTRACT

It is shown in this paper that the weighted domination problem and its two variants, the weighted connected domination and weighted total domination problems are NP-complete on cocomparability graphs when arbitrary integer vertex weights are allowed and all of them can be solved in polynomial time if vertex weights are integers and less than or equal to a constant c. Besides, an O(¦V¦2) algorithm is given for the weighted independent perfect domination problem of a cocomparability graph G=(V, E). More... »

PAGES

122-131

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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 and Information Engineering, National Chung Cheng University, Min-Hsiun, Chiayi, 621, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Min-Hsiun, Chiayi, 621, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Maw-Shang", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "It is shown in this paper that the weighted domination problem and its two variants, the weighted connected domination and weighted total domination problems are NP-complete on cocomparability graphs when arbitrary integer vertex weights are allowed and all of them can be solved in polynomial time if vertex weights are integers and less than or equal to a constant c. Besides, an O(\u00a6V\u00a62) algorithm is given for the weighted independent perfect domination problem of a cocomparability graph G=(V, E).", 
    "editor": [
      {
        "familyName": "Staples", 
        "givenName": "John", 
        "type": "Person"
      }, 
      {
        "familyName": "Eades", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Katoh", 
        "givenName": "Naoki", 
        "type": "Person"
      }, 
      {
        "familyName": "Moffat", 
        "givenName": "Alistair", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0015415", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-60573-7", 
        "978-3-540-47766-2"
      ], 
      "name": "Algorithms and Computations", 
      "type": "Book"
    }, 
    "keywords": [
      "cocomparability graphs", 
      "domination problem", 
      "vertex weights", 
      "connected domination", 
      "polynomial time", 
      "graph", 
      "total domination problem", 
      "algorithm", 
      "NP", 
      "integers", 
      "time", 
      "variants", 
      "weight", 
      "domination", 
      "paper", 
      "problem", 
      "weighted domination problem", 
      "arbitrary integer vertex weights", 
      "integer vertex weights", 
      "independent perfect domination problem", 
      "perfect domination problem"
    ], 
    "name": "Weighted domination on cocomparability graphs", 
    "pagination": "122-131", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035705709"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0015415"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0015415", 
      "https://app.dimensions.ai/details/publication/pub.1035705709"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_244.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0015415"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

96 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0015415 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1b8af199ea59409087867ab029ef595b
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description It is shown in this paper that the weighted domination problem and its two variants, the weighted connected domination and weighted total domination problems are NP-complete on cocomparability graphs when arbitrary integer vertex weights are allowed and all of them can be solved in polynomial time if vertex weights are integers and less than or equal to a constant c. Besides, an O(¦V¦2) algorithm is given for the weighted independent perfect domination problem of a cocomparability graph G=(V, E).
7 schema:editor N8df5eb86a3e942f58019035c2567f75c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd10b53cbdd5b4b55bd7aa6f98aba9500
12 schema:keywords NP
13 algorithm
14 arbitrary integer vertex weights
15 cocomparability graphs
16 connected domination
17 domination
18 domination problem
19 graph
20 independent perfect domination problem
21 integer vertex weights
22 integers
23 paper
24 perfect domination problem
25 polynomial time
26 problem
27 time
28 total domination problem
29 variants
30 vertex weights
31 weight
32 weighted domination problem
33 schema:name Weighted domination on cocomparability graphs
34 schema:pagination 122-131
35 schema:productId Nc3bb389dac2b4c01b65445fe7c932840
36 Ndff75e1904264c0598a1a0732ce0449b
37 schema:publisher N47b77f95285c4f67befe014aeb8f2dec
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035705709
39 https://doi.org/10.1007/bfb0015415
40 schema:sdDatePublished 2022-01-01T19:14
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N5f1566ec6c8a4dd9a7f3a93a851b1306
43 schema:url https://doi.org/10.1007/bfb0015415
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N1b8af199ea59409087867ab029ef595b rdf:first sg:person.013174232477.45
48 rdf:rest rdf:nil
49 N47b77f95285c4f67befe014aeb8f2dec schema:name Springer Nature
50 rdf:type schema:Organisation
51 N55f31ead77ee4ce186c75a85551c0cfd rdf:first N5a7a6b93342048e1aeff01ad45508995
52 rdf:rest N8cc592464262464fbc681e6f9bee4a0d
53 N5a7a6b93342048e1aeff01ad45508995 schema:familyName Katoh
54 schema:givenName Naoki
55 rdf:type schema:Person
56 N5f1566ec6c8a4dd9a7f3a93a851b1306 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N8cc592464262464fbc681e6f9bee4a0d rdf:first Nf1ab0ebdab064ef98f47d6d2d1b4d69e
59 rdf:rest rdf:nil
60 N8df5eb86a3e942f58019035c2567f75c rdf:first Nb0815f9e228f4eb9b4b11be12a0e6210
61 rdf:rest Ncdb976e7dff648b3b90675c55c29d91a
62 Nb0815f9e228f4eb9b4b11be12a0e6210 schema:familyName Staples
63 schema:givenName John
64 rdf:type schema:Person
65 Nc3bb389dac2b4c01b65445fe7c932840 schema:name doi
66 schema:value 10.1007/bfb0015415
67 rdf:type schema:PropertyValue
68 Ncdb976e7dff648b3b90675c55c29d91a rdf:first Nd44f7dcd8b78438786951029f017c429
69 rdf:rest N55f31ead77ee4ce186c75a85551c0cfd
70 Nd10b53cbdd5b4b55bd7aa6f98aba9500 schema:isbn 978-3-540-47766-2
71 978-3-540-60573-7
72 schema:name Algorithms and Computations
73 rdf:type schema:Book
74 Nd44f7dcd8b78438786951029f017c429 schema:familyName Eades
75 schema:givenName Peter
76 rdf:type schema:Person
77 Ndff75e1904264c0598a1a0732ce0449b schema:name dimensions_id
78 schema:value pub.1035705709
79 rdf:type schema:PropertyValue
80 Nf1ab0ebdab064ef98f47d6d2d1b4d69e schema:familyName Moffat
81 schema:givenName Alistair
82 rdf:type schema:Person
83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information and Computing Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
87 schema:name Computation Theory and Mathematics
88 rdf:type schema:DefinedTerm
89 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
90 schema:familyName Chang
91 schema:givenName Maw-Shang
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
93 rdf:type schema:Person
94 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, Min-Hsiun, Chiayi, 621, Taiwan, Republic of China
95 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, Min-Hsiun, Chiayi, 621, Taiwan, Republic of China
96 rdf:type schema:Organization
 




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


...