Approximation Algorithms for Independent Sets in Map Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000-07-21

AUTHORS

Zhi-Zhong Chen

ABSTRACT

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well. More... »

PAGES

105-114

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44968-x_11

DOI

http://dx.doi.org/10.1007/3-540-44968-x_11

DIMENSIONS

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


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 Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000-07-21", 
    "datePublishedReg": "2000-07-21", 
    "description": "This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+\u03b4 can be achieved in O(n2) time for any given constant \u03b4 > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Eades", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Estivill-Castro", 
        "givenName": "Vladimir", 
        "type": "Person"
      }, 
      {
        "familyName": "Lin", 
        "givenName": "Xuemin", 
        "type": "Person"
      }, 
      {
        "familyName": "Sharma", 
        "givenName": "Arun", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44968-x_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67787-1", 
        "978-3-540-44968-3"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "map graphs", 
      "approximation algorithm", 
      "polynomial-time approximation algorithm", 
      "maximum independent set", 
      "best approximation algorithm", 
      "independent set", 
      "fundamental results", 
      "vertex cover", 
      "case G", 
      "graph G", 
      "algorithm", 
      "graph", 
      "vertices", 
      "set", 
      "problem", 
      "maps", 
      "coloring", 
      "applications", 
      "time", 
      "design", 
      "results", 
      "ratio", 
      "weight", 
      "cover", 
      "paper"
    ], 
    "name": "Approximation Algorithms for Independent Sets in Map Graphs", 
    "pagination": "105-114", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039882777"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44968-x_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44968-x_11", 
      "https://app.dimensions.ai/details/publication/pub.1039882777"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:36", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_115.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44968-x_11"
  }
]
 

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-44968-x_11'

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-44968-x_11'

Turtle is a human-readable linked data format.

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

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-44968-x_11'


 

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

105 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44968-x_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd7b563218cbb4f0692c188802f765e64
4 schema:datePublished 2000-07-21
5 schema:datePublishedReg 2000-07-21
6 schema:description This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.
7 schema:editor N8dd7cbf295da454cb42c1d8c6097c77f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N86f8255d911e4d4aa20db412ec9c4881
12 schema:keywords algorithm
13 applications
14 approximation algorithm
15 best approximation algorithm
16 case G
17 coloring
18 cover
19 design
20 fundamental results
21 graph
22 graph G
23 independent set
24 map graphs
25 maps
26 maximum independent set
27 paper
28 polynomial-time approximation algorithm
29 problem
30 ratio
31 results
32 set
33 time
34 vertex cover
35 vertices
36 weight
37 schema:name Approximation Algorithms for Independent Sets in Map Graphs
38 schema:pagination 105-114
39 schema:productId Na3f723427be74ea197f3cfd5acde704b
40 Nf74e4ae5dc864d6495834e21b69946f8
41 schema:publisher N7ccc2d42f0974334b6e44003db25a170
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039882777
43 https://doi.org/10.1007/3-540-44968-x_11
44 schema:sdDatePublished 2022-05-10T10:36
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N563e460722ab480faff0a7ad3b7d275b
47 schema:url https://doi.org/10.1007/3-540-44968-x_11
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N2c7877435ff1457589e81679b649f071 schema:familyName Estivill-Castro
52 schema:givenName Vladimir
53 rdf:type schema:Person
54 N40c89249a5d74e57b135663d84ef8443 schema:familyName Lin
55 schema:givenName Xuemin
56 rdf:type schema:Person
57 N5260c809a6824f62b1ae75ad6c64aa02 rdf:first N2c7877435ff1457589e81679b649f071
58 rdf:rest Na8774a434b234496883c5e4e8f123ff0
59 N547515390eb64a9b866bb01a35125bd0 schema:familyName Sharma
60 schema:givenName Arun
61 rdf:type schema:Person
62 N563e460722ab480faff0a7ad3b7d275b schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N6c33c158926940118b794afeaab5e87f rdf:first N547515390eb64a9b866bb01a35125bd0
65 rdf:rest rdf:nil
66 N7ccc2d42f0974334b6e44003db25a170 schema:name Springer Nature
67 rdf:type schema:Organisation
68 N86f8255d911e4d4aa20db412ec9c4881 schema:isbn 978-3-540-44968-3
69 978-3-540-67787-1
70 schema:name Computing and Combinatorics
71 rdf:type schema:Book
72 N8dd7cbf295da454cb42c1d8c6097c77f rdf:first Na63d111fd62f4ec4b2af6fa07ffe9c7e
73 rdf:rest N93d5ffa648ab4ec2936c391be182643c
74 N93d5ffa648ab4ec2936c391be182643c rdf:first Nd453badbf56f4bfaad520d84500c9a1e
75 rdf:rest N5260c809a6824f62b1ae75ad6c64aa02
76 Na3f723427be74ea197f3cfd5acde704b schema:name doi
77 schema:value 10.1007/3-540-44968-x_11
78 rdf:type schema:PropertyValue
79 Na63d111fd62f4ec4b2af6fa07ffe9c7e schema:familyName Du
80 schema:givenName Ding-Zhu
81 rdf:type schema:Person
82 Na8774a434b234496883c5e4e8f123ff0 rdf:first N40c89249a5d74e57b135663d84ef8443
83 rdf:rest N6c33c158926940118b794afeaab5e87f
84 Nd453badbf56f4bfaad520d84500c9a1e schema:familyName Eades
85 schema:givenName Peter
86 rdf:type schema:Person
87 Nd7b563218cbb4f0692c188802f765e64 rdf:first sg:person.015654265661.98
88 rdf:rest rdf:nil
89 Nf74e4ae5dc864d6495834e21b69946f8 schema:name dimensions_id
90 schema:value pub.1039882777
91 rdf:type schema:PropertyValue
92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
93 schema:name Information and Computing Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
96 schema:name Computation Theory and Mathematics
97 rdf:type schema:DefinedTerm
98 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
99 schema:familyName Chen
100 schema:givenName Zhi-Zhong
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
102 rdf:type schema:Person
103 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
104 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
105 rdf:type schema:Organization
 




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


...