Improved approximations of independent dominating set in bounded degree graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Paola Alimonti , Tiziana Calamoneri

ABSTRACT

We consider the problem of finding an independent dominating set of minimum cardinality in bounded degree and regular graphs. We first give approximate heuristics for MIDS in cubic and at most cubic graphs, based on greedy and local search techniques. Then, we consider graphs of bounded degree B and B-regular graphs, for B ≥ 4. In particular, the greedy phase proposed for at most cubic graphs is extended to any B and iteratively repeated until the degree of the remaining graph is greater than 3. Finally, the algorithm for at most cubic graphs is executed. Our algorithms achieve approximation ratios: More... »

PAGES

2-16

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-62559-9
978-3-540-68072-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-62559-3_2

DOI

http://dx.doi.org/10.1007/3-540-62559-3_2

DIMENSIONS

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


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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, 00198\u00a0Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alimonti", 
        "givenName": "Paola", 
        "id": "sg:person.015632520461.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell'Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, 00198\u00a0Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Calamoneri", 
        "givenName": "Tiziana", 
        "id": "sg:person.013577775161.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "We consider the problem of finding an independent dominating set of minimum cardinality in bounded degree and regular graphs. We first give approximate heuristics for MIDS in cubic and at most cubic graphs, based on greedy and local search techniques. Then, we consider graphs of bounded degree B and B-regular graphs, for B \u2265 4. In particular, the greedy phase proposed for at most cubic graphs is extended to any B and iteratively repeated until the degree of the remaining graph is greater than 3. Finally, the algorithm for at most cubic graphs is executed. Our algorithms achieve approximation ratios:", 
    "editor": [
      {
        "familyName": "d'Amore", 
        "givenName": "Fabrizio", 
        "type": "Person"
      }, 
      {
        "familyName": "Franciosa", 
        "givenName": "Paolo Giulio", 
        "type": "Person"
      }, 
      {
        "familyName": "Marchetti-Spaccamela", 
        "givenName": "Alberto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-62559-3_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-62559-9", 
        "978-3-540-68072-7"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "name": "Improved approximations of independent dominating set in bounded degree graphs", 
    "pagination": "2-16", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-62559-3_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c17ef2c51f4d69929f493ee8c20e837625ebd3209ca44bccad4f54c9d856b7ac"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040619460"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-62559-3_2", 
      "https://app.dimensions.ai/details/publication/pub.1040619460"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:22", 
    "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_8660_00000069.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-62559-3_2"
  }
]
 

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-62559-3_2'

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-62559-3_2'

Turtle is a human-readable linked data format.

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

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-62559-3_2'


 

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

83 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-62559-3_2 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na622142931d14e869abf3315e2c3084c
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description We consider the problem of finding an independent dominating set of minimum cardinality in bounded degree and regular graphs. We first give approximate heuristics for MIDS in cubic and at most cubic graphs, based on greedy and local search techniques. Then, we consider graphs of bounded degree B and B-regular graphs, for B ≥ 4. In particular, the greedy phase proposed for at most cubic graphs is extended to any B and iteratively repeated until the degree of the remaining graph is greater than 3. Finally, the algorithm for at most cubic graphs is executed. Our algorithms achieve approximation ratios:
7 schema:editor N293cff745a8746e98424980e45031635
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Na84bc64b70164963b934da87340acbe3
12 schema:name Improved approximations of independent dominating set in bounded degree graphs
13 schema:pagination 2-16
14 schema:productId N281c5f494d1f4c05b72a977cbc3a1680
15 Nb269518d4b1f45dda506b173d4649f39
16 Nbd53d0e2ef554c1da43420c9f648f6c8
17 schema:publisher N49e18d5916ac4ea383514fa8bc570c8d
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040619460
19 https://doi.org/10.1007/3-540-62559-3_2
20 schema:sdDatePublished 2019-04-15T11:22
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N5894a7a1dfcf4b728dd6dbe30691348a
23 schema:url http://link.springer.com/10.1007/3-540-62559-3_2
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N281c5f494d1f4c05b72a977cbc3a1680 schema:name readcube_id
28 schema:value c17ef2c51f4d69929f493ee8c20e837625ebd3209ca44bccad4f54c9d856b7ac
29 rdf:type schema:PropertyValue
30 N293cff745a8746e98424980e45031635 rdf:first Ndbef7574926f4f42a432a897ba182483
31 rdf:rest Nb0eefee8fbda47e0adced6598a21d193
32 N49e18d5916ac4ea383514fa8bc570c8d schema:location Berlin, Heidelberg
33 schema:name Springer Berlin Heidelberg
34 rdf:type schema:Organisation
35 N4b8b25054c2c459e9006734e4b60dd83 rdf:first sg:person.013577775161.22
36 rdf:rest rdf:nil
37 N5894a7a1dfcf4b728dd6dbe30691348a schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N78d7d92866c64186a3ca2e2b9155a929 schema:familyName Franciosa
40 schema:givenName Paolo Giulio
41 rdf:type schema:Person
42 Na622142931d14e869abf3315e2c3084c rdf:first sg:person.015632520461.69
43 rdf:rest N4b8b25054c2c459e9006734e4b60dd83
44 Na84bc64b70164963b934da87340acbe3 schema:isbn 978-3-540-62559-9
45 978-3-540-68072-7
46 schema:name Graph-Theoretic Concepts in Computer Science
47 rdf:type schema:Book
48 Nb0eefee8fbda47e0adced6598a21d193 rdf:first N78d7d92866c64186a3ca2e2b9155a929
49 rdf:rest Nca198c755f214dad9390e14938d6664f
50 Nb269518d4b1f45dda506b173d4649f39 schema:name doi
51 schema:value 10.1007/3-540-62559-3_2
52 rdf:type schema:PropertyValue
53 Nbd53d0e2ef554c1da43420c9f648f6c8 schema:name dimensions_id
54 schema:value pub.1040619460
55 rdf:type schema:PropertyValue
56 Nca198c755f214dad9390e14938d6664f rdf:first Ne7746e00ee964fcf9ea1195c9a1678dc
57 rdf:rest rdf:nil
58 Ndbef7574926f4f42a432a897ba182483 schema:familyName d'Amore
59 schema:givenName Fabrizio
60 rdf:type schema:Person
61 Ne7746e00ee964fcf9ea1195c9a1678dc schema:familyName Marchetti-Spaccamela
62 schema:givenName Alberto
63 rdf:type schema:Person
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
71 schema:familyName Calamoneri
72 schema:givenName Tiziana
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
74 rdf:type schema:Person
75 sg:person.015632520461.69 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
76 schema:familyName Alimonti
77 schema:givenName Paola
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
81 schema:name Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, via Salaria 113, 00198 Roma, Italy
82 Dipartimento di Scienze dell'Informazione, Università di Roma “La Sapienza”, via Salaria 113, 00198 Roma, Italy
83 rdf:type schema:Organization
 




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


...