Efficient Minus and Signed Domination in Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Chin Lung Lu , Sheng-Lung Peng , Chuan Yi Tang

ABSTRACT

We show that the efficient minus (resp., signed) domination problem is NP-complete for chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (resp., for chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (resp., every graph with no vertex of odd degree) has an efficient minus (resp., signed) dominating function. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees. More... »

PAGES

241-253

Book

TITLE

Algorithms and Computation

ISBN

978-3-540-41255-7
978-3-540-40996-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-40996-3_21

DOI

http://dx.doi.org/10.1007/3-540-40996-3_21

DIMENSIONS

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


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": {
          "alternateName": "National Center for High-Performance Computing", 
          "id": "https://www.grid.ac/institutes/grid.462649.b", 
          "name": [
            "National Center for High-Performance Computing, P.O. Box 19-136, 300\u00a0Hsinchu, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Chin Lung", 
        "id": "sg:person.016502771037.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Computer Science and Information Engineering, National DongHwa University, Hualien, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Peng", 
        "givenName": "Sheng-Lung", 
        "id": "sg:person.013531324035.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31"
        ], 
        "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, 300\u00a0Hsinchu, Taiwan, R.O.C"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Chuan Yi", 
        "id": "sg:person.01312526135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0166-218x(94)00138-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008488311"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(95)00094-d", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012284170"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(94)00067-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021069871"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(93)90147-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026550422"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(95)00056-w", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027769676"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "We show that the efficient minus (resp., signed) domination problem is NP-complete for chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (resp., for chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (resp., every graph with no vertex of odd degree) has an efficient minus (resp., signed) dominating function. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees.", 
    "editor": [
      {
        "familyName": "Goos", 
        "givenName": "Gerhard", 
        "type": "Person"
      }, 
      {
        "familyName": "Hartmanis", 
        "givenName": "Juris", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "D. T.", 
        "type": "Person"
      }, 
      {
        "familyName": "Teng", 
        "givenName": "Shang-Hua", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-40996-3_21", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41255-7", 
        "978-3-540-40996-0"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Efficient Minus and Signed Domination in Graphs", 
    "pagination": "241-253", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-40996-3_21"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d5ef3b7851d4a5fd59a976bda0fdf7a893a6ff06f77350415f2e182c6f5d109c"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044913019"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-40996-3_21", 
      "https://app.dimensions.ai/details/publication/pub.1044913019"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T18:13", 
    "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_8681_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-40996-3_21"
  }
]
 

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/3-540-40996-3_21'

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/3-540-40996-3_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-40996-3_21'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-40996-3_21'


 

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

119 TRIPLES      23 PREDICATES      32 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-40996-3_21 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9afc6add37e84bb58b6f84a259e96762
4 schema:citation https://doi.org/10.1016/0012-365x(95)00094-d
5 https://doi.org/10.1016/0020-0190(93)90147-2
6 https://doi.org/10.1016/0166-218x(94)00067-3
7 https://doi.org/10.1016/0166-218x(94)00138-4
8 https://doi.org/10.1016/0166-218x(95)00056-w
9 schema:datePublished 2000
10 schema:datePublishedReg 2000-01-01
11 schema:description We show that the efficient minus (resp., signed) domination problem is NP-complete for chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (resp., for chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (resp., every graph with no vertex of odd degree) has an efficient minus (resp., signed) dominating function. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees.
12 schema:editor Nc47c7af3dcd24c478794a31e64ab5b30
13 schema:genre chapter
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N66a68a032b1c433494681ffb11a2b14e
17 schema:name Efficient Minus and Signed Domination in Graphs
18 schema:pagination 241-253
19 schema:productId N22c7ee008bf549f09bc80efd051a0732
20 N72f7a3df6713463f94fee12fed01c266
21 Nf55374c16df5444fa6e2a771b1792e51
22 schema:publisher N63b1aadfdadc4eb9b46847f701119d23
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044913019
24 https://doi.org/10.1007/3-540-40996-3_21
25 schema:sdDatePublished 2019-04-15T18:13
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher Nbeead14dfc0c43d9ba6d785367406c9a
28 schema:url http://link.springer.com/10.1007/3-540-40996-3_21
29 sgo:license sg:explorer/license/
30 sgo:sdDataset chapters
31 rdf:type schema:Chapter
32 N091df139b17245868d7a0ccb2a6f4228 rdf:first sg:person.01312526135.27
33 rdf:rest rdf:nil
34 N22c7ee008bf549f09bc80efd051a0732 schema:name readcube_id
35 schema:value d5ef3b7851d4a5fd59a976bda0fdf7a893a6ff06f77350415f2e182c6f5d109c
36 rdf:type schema:PropertyValue
37 N31d247f63ae748e9aada6a5364a59470 schema:familyName Lee
38 schema:givenName D. T.
39 rdf:type schema:Person
40 N63b1aadfdadc4eb9b46847f701119d23 schema:location Berlin, Heidelberg
41 schema:name Springer Berlin Heidelberg
42 rdf:type schema:Organisation
43 N66a68a032b1c433494681ffb11a2b14e schema:isbn 978-3-540-40996-0
44 978-3-540-41255-7
45 schema:name Algorithms and Computation
46 rdf:type schema:Book
47 N6a2030f9379b459c8af47e47e967d7d8 schema:name Department of Computer Science and Information Engineering, National DongHwa University, Hualien, Taiwan, R.O.C
48 rdf:type schema:Organization
49 N6a280e6c023a4b2ebe75aca6a001154b rdf:first N9209fdd4898d4698894e4f352c758a07
50 rdf:rest N83bdcd5ad34e438281231493fe969ff0
51 N72f7a3df6713463f94fee12fed01c266 schema:name dimensions_id
52 schema:value pub.1044913019
53 rdf:type schema:PropertyValue
54 N83bdcd5ad34e438281231493fe969ff0 rdf:first Ne47efecf041545f4b5a64693f63249df
55 rdf:rest Nd211fdfb91b448d88c571dfb512a85c3
56 N9209fdd4898d4698894e4f352c758a07 schema:familyName Hartmanis
57 schema:givenName Juris
58 rdf:type schema:Person
59 N9afc6add37e84bb58b6f84a259e96762 rdf:first sg:person.016502771037.22
60 rdf:rest Nf69cc12ce415487bb9553a7b944c2e61
61 Nbeead14dfc0c43d9ba6d785367406c9a schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 Nc47c7af3dcd24c478794a31e64ab5b30 rdf:first Nd47336094ab44e8583beb104383daf71
64 rdf:rest N6a280e6c023a4b2ebe75aca6a001154b
65 Nd211fdfb91b448d88c571dfb512a85c3 rdf:first N31d247f63ae748e9aada6a5364a59470
66 rdf:rest Nf42e1396def84431b4c30baaa651934f
67 Nd47336094ab44e8583beb104383daf71 schema:familyName Goos
68 schema:givenName Gerhard
69 rdf:type schema:Person
70 Ne47efecf041545f4b5a64693f63249df schema:familyName van Leeuwen
71 schema:givenName Jan
72 rdf:type schema:Person
73 Nf2a0e9db834b482f88bbcbd0e6040d57 schema:familyName Teng
74 schema:givenName Shang-Hua
75 rdf:type schema:Person
76 Nf42e1396def84431b4c30baaa651934f rdf:first Nf2a0e9db834b482f88bbcbd0e6040d57
77 rdf:rest rdf:nil
78 Nf55374c16df5444fa6e2a771b1792e51 schema:name doi
79 schema:value 10.1007/3-540-40996-3_21
80 rdf:type schema:PropertyValue
81 Nf69cc12ce415487bb9553a7b944c2e61 rdf:first sg:person.013531324035.31
82 rdf:rest N091df139b17245868d7a0ccb2a6f4228
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.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
90 schema:familyName Tang
91 schema:givenName Chuan Yi
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
93 rdf:type schema:Person
94 sg:person.013531324035.31 schema:affiliation N6a2030f9379b459c8af47e47e967d7d8
95 schema:familyName Peng
96 schema:givenName Sheng-Lung
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013531324035.31
98 rdf:type schema:Person
99 sg:person.016502771037.22 schema:affiliation https://www.grid.ac/institutes/grid.462649.b
100 schema:familyName Lu
101 schema:givenName Chin Lung
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22
103 rdf:type schema:Person
104 https://doi.org/10.1016/0012-365x(95)00094-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1012284170
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/0020-0190(93)90147-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026550422
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/0166-218x(94)00067-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021069871
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0166-218x(94)00138-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008488311
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0166-218x(95)00056-w schema:sameAs https://app.dimensions.ai/details/publication/pub.1027769676
113 rdf:type schema:CreativeWork
114 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
115 schema:name Department of Computer Science, National Tsing Hua University, 300 Hsinchu, Taiwan, R.O.C
116 rdf:type schema:Organization
117 https://www.grid.ac/institutes/grid.462649.b schema:alternateName National Center for High-Performance Computing
118 schema:name National Center for High-Performance Computing, P.O. Box 19-136, 300 Hsinchu, Taiwan, R.O.C
119 rdf:type schema:Organization
 




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


...