Efficient domination on permutation graphs and trapezoid graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Y. Daniel Liang , Chin Lung Lu , Chuan Yi Tang

ABSTRACT

The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + \(\bar m\)) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + \(\bar m\)) algorithm on trapezoid graphs, where \(\bar m\)denotes the number of edges in the complement of G. More... »

PAGES

232-241

References to SciGraph publications

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-63357-0
978-3-540-69522-6

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Purdue University", 
          "id": "https://www.grid.ac/institutes/grid.169077.e", 
          "name": [
            "Department of Computer Science, Indiana Purdue University at Fort Wayne, 46805\u00a0Fort Wayne, IN"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liang", 
        "givenName": "Y. Daniel", 
        "id": "sg:person.016645121673.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645121673.71"
        ], 
        "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, 30043\u00a0Hsin-Chu, 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": {
          "alternateName": "National Tsing Hua University", 
          "id": "https://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, 30043\u00a0Hsin-Chu, 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.1017/cbo9780511662072.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009389496"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(88)90032-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013716111"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-69672-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017862861", 
          "https://doi.org/10.1007/978-3-642-69672-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-69672-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017862861", 
          "https://doi.org/10.1007/978-3-642-69672-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(94)00158-a", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040564106"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(73)90042-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044510915"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1971-016-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072265451"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + \\(\\bar m\\)) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + \\(\\bar m\\)) algorithm on trapezoid graphs, where \\(\\bar m\\)denotes the number of edges in the complement of G.", 
    "editor": [
      {
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "D. T.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0045090", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63357-0", 
        "978-3-540-69522-6"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "Efficient domination on permutation graphs and trapezoid graphs", 
    "pagination": "232-241", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0045090"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d08805ed799f6cddc02e42b7ce0462a32af667d01f5badfcadff3a4a607c4dd6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043777918"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0045090", 
      "https://app.dimensions.ai/details/publication/pub.1043777918"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:41", 
    "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_8697_00000075.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/BFb0045090"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

106 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0045090 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N44863ffd6bd2432389ce8689525d64e6
4 schema:citation sg:pub.10.1007/978-3-642-69672-5
5 https://doi.org/10.1016/0095-8956(73)90042-7
6 https://doi.org/10.1016/0166-218x(88)90032-7
7 https://doi.org/10.1016/0166-218x(94)00158-a
8 https://doi.org/10.1017/cbo9780511662072.002
9 https://doi.org/10.4153/cjm-1971-016-5
10 schema:datePublished 1997
11 schema:datePublishedReg 1997-01-01
12 schema:description The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + \(\bar m\)) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + \(\bar m\)) algorithm on trapezoid graphs, where \(\bar m\)denotes the number of edges in the complement of G.
13 schema:editor N89de11a2905846f9b6e18dba0eaa5c19
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf N5762a3e664bf4d119655d7143f103172
18 schema:name Efficient domination on permutation graphs and trapezoid graphs
19 schema:pagination 232-241
20 schema:productId N50039128a103438b8145e97ab55a0e9e
21 N76e9d39bfccb4b48955b0fdffe478f31
22 N7a16da6469e04195a192d4df84998953
23 schema:publisher N1b1d507e42b347f8a2ede8511381f56e
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043777918
25 https://doi.org/10.1007/bfb0045090
26 schema:sdDatePublished 2019-04-15T23:41
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N58b92dd214104f2d83810b84a691f667
29 schema:url http://link.springer.com/10.1007/BFb0045090
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N06fc29d3b75d4c159dfc38380f475ee3 schema:familyName Jiang
34 schema:givenName Tao
35 rdf:type schema:Person
36 N1b1d507e42b347f8a2ede8511381f56e schema:location Berlin, Heidelberg
37 schema:name Springer Berlin Heidelberg
38 rdf:type schema:Organisation
39 N44863ffd6bd2432389ce8689525d64e6 rdf:first sg:person.016645121673.71
40 rdf:rest N684bbafaefe24c80bccc2a34c459c072
41 N50039128a103438b8145e97ab55a0e9e schema:name doi
42 schema:value 10.1007/bfb0045090
43 rdf:type schema:PropertyValue
44 N5762a3e664bf4d119655d7143f103172 schema:isbn 978-3-540-63357-0
45 978-3-540-69522-6
46 schema:name Computing and Combinatorics
47 rdf:type schema:Book
48 N576c4d9f388843deaba9fe1913a54561 schema:familyName Lee
49 schema:givenName D. T.
50 rdf:type schema:Person
51 N58b92dd214104f2d83810b84a691f667 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N684bbafaefe24c80bccc2a34c459c072 rdf:first sg:person.016502771037.22
54 rdf:rest Ne222416f847f49e1994f87c98ae6bde3
55 N76e9d39bfccb4b48955b0fdffe478f31 schema:name readcube_id
56 schema:value d08805ed799f6cddc02e42b7ce0462a32af667d01f5badfcadff3a4a607c4dd6
57 rdf:type schema:PropertyValue
58 N7a16da6469e04195a192d4df84998953 schema:name dimensions_id
59 schema:value pub.1043777918
60 rdf:type schema:PropertyValue
61 N89de11a2905846f9b6e18dba0eaa5c19 rdf:first N06fc29d3b75d4c159dfc38380f475ee3
62 rdf:rest Ne359aefb71d44ec88a54314cdca4ffc3
63 Ne222416f847f49e1994f87c98ae6bde3 rdf:first sg:person.01312526135.27
64 rdf:rest rdf:nil
65 Ne359aefb71d44ec88a54314cdca4ffc3 rdf:first N576c4d9f388843deaba9fe1913a54561
66 rdf:rest rdf:nil
67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
68 schema:name Information and Computing Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
71 schema:name Computation Theory and Mathematics
72 rdf:type schema:DefinedTerm
73 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
74 schema:familyName Tang
75 schema:givenName Chuan Yi
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
77 rdf:type schema:Person
78 sg:person.016502771037.22 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
79 schema:familyName Lu
80 schema:givenName Chin Lung
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22
82 rdf:type schema:Person
83 sg:person.016645121673.71 schema:affiliation https://www.grid.ac/institutes/grid.169077.e
84 schema:familyName Liang
85 schema:givenName Y. Daniel
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645121673.71
87 rdf:type schema:Person
88 sg:pub.10.1007/978-3-642-69672-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017862861
89 https://doi.org/10.1007/978-3-642-69672-5
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/0095-8956(73)90042-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044510915
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/0166-218x(88)90032-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013716111
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/0166-218x(94)00158-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1040564106
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1017/cbo9780511662072.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009389496
98 rdf:type schema:CreativeWork
99 https://doi.org/10.4153/cjm-1971-016-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072265451
100 rdf:type schema:CreativeWork
101 https://www.grid.ac/institutes/grid.169077.e schema:alternateName Purdue University
102 schema:name Department of Computer Science, Indiana Purdue University at Fort Wayne, 46805 Fort Wayne, IN
103 rdf:type schema:Organization
104 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
105 schema:name Department of Computer Science, National Tsing Hua University, 30043 Hsin-Chu, Taiwan, R.O.C.
106 rdf:type schema:Organization
 




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


...