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": "2021-11-01T18:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_356.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 Naedeb4e43f3949deb3a5e6102f97db98
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 N6c6070b0e2f54906af950acc847e91b3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Na335c031deb0432e97a2eeb5857c1a70
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 N998be47f74c4445f86c57c755d60e82b
36 Nd016d40ead5b453f8c50b7a875984b81
37 schema:publisher Nf05b469a508d47a39e837c9309588a89
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035705709
39 https://doi.org/10.1007/bfb0015415
40 schema:sdDatePublished 2021-11-01T18:57
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N4b567974b13d4012b93b9a3084f9c386
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 N0a3588025c394bf9be2dae8f8786203b rdf:first N49ad00c70a5849b08e76191fc46610a1
48 rdf:rest rdf:nil
49 N3cc00688959b478cacfc76a46a429c1b schema:familyName Staples
50 schema:givenName John
51 rdf:type schema:Person
52 N49ad00c70a5849b08e76191fc46610a1 schema:familyName Moffat
53 schema:givenName Alistair
54 rdf:type schema:Person
55 N4b567974b13d4012b93b9a3084f9c386 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 N6c6070b0e2f54906af950acc847e91b3 rdf:first N3cc00688959b478cacfc76a46a429c1b
58 rdf:rest N7487213079cd48919e9bca8ce7e364c2
59 N6efa2aea1dbe4b7c83066aa99e63928c schema:familyName Katoh
60 schema:givenName Naoki
61 rdf:type schema:Person
62 N7487213079cd48919e9bca8ce7e364c2 rdf:first N9c6c000eb436495f99964ae944a34252
63 rdf:rest Nd72095d54daa41ebacc50233f1d9fc9d
64 N998be47f74c4445f86c57c755d60e82b schema:name doi
65 schema:value 10.1007/bfb0015415
66 rdf:type schema:PropertyValue
67 N9c6c000eb436495f99964ae944a34252 schema:familyName Eades
68 schema:givenName Peter
69 rdf:type schema:Person
70 Na335c031deb0432e97a2eeb5857c1a70 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 Naedeb4e43f3949deb3a5e6102f97db98 rdf:first sg:person.013174232477.45
75 rdf:rest rdf:nil
76 Nd016d40ead5b453f8c50b7a875984b81 schema:name dimensions_id
77 schema:value pub.1035705709
78 rdf:type schema:PropertyValue
79 Nd72095d54daa41ebacc50233f1d9fc9d rdf:first N6efa2aea1dbe4b7c83066aa99e63928c
80 rdf:rest N0a3588025c394bf9be2dae8f8786203b
81 Nf05b469a508d47a39e837c9309588a89 schema:name Springer Nature
82 rdf:type schema:Organisation
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)


...