An Optimal Labeling for Node Connectivity View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Tai-Hsin Hsu , Hsueh-I Lu

ABSTRACT

Given an n-node undirected simple graph G and a positive integer k, the k-connectivity labeling problem for G seeks short labels for the nodes of G such that whether any two nodes are k-connected in G can be determined merely by their labels. For k = 1, an optimal solution to the problem is to give each node in the same connected component of G a common ⌈log2n⌉-bit label, uniquely chosen for this connected component. For k ≥ 2, Katz, Katz, Korman, and Peleg gave the first nontrivial solution to the problem, requiring O(2klogn) bits per node. The best previously known solution, due to Korman, requires O(k2logn) bits per node. We give the first asymptotically optimal solution to the problem, requiring only \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(2k-1)\left\lceil\log_2 n\right\rceil$\end{document} bits per node, which matches a lower bound Ω(klogn) proved by Katz, Katz, Korman, and Peleg. More... »

PAGES

303-310

Book

TITLE

Algorithms and Computation

ISBN

978-3-642-10630-9
978-3-642-10631-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_32

DOI

http://dx.doi.org/10.1007/978-3-642-10631-6_32

DIMENSIONS

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


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/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Public Health and Health Services", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hsu", 
        "givenName": "Tai-Hsin", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Given an n-node undirected simple graph G and a positive integer k, the k-connectivity labeling problem for G seeks short labels for the nodes of G such that whether any two nodes are k-connected in G can be determined merely by their labels. For k\u2009=\u20091, an optimal solution to the problem is to give each node in the same connected component of G a common \u2308log2n\u2309-bit label, uniquely chosen for this connected component. For k\u2009\u2265\u20092, Katz, Katz, Korman, and Peleg gave the first nontrivial solution to the problem, requiring O(2klogn) bits per node. The best previously known solution, due to Korman, requires O(k2logn) bits per node. We give the first asymptotically optimal solution to the problem, requiring only \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$(2k-1)\\left\\lceil\\log_2 n\\right\\rceil$\\end{document} bits per node, which matches a lower bound \u03a9(klogn) proved by Katz, Katz, Korman, and Peleg.", 
    "editor": [
      {
        "familyName": "Dong", 
        "givenName": "Yingfei", 
        "type": "Person"
      }, 
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-10631-6_32", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-10630-9", 
        "978-3-642-10631-6"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "nodes", 
      "labeling", 
      "labels", 
      "components", 
      "optimal labeling", 
      "connectivity", 
      "Katz", 
      "problem", 
      "Korman", 
      "solution", 
      "node connectivity", 
      "bits", 
      "short labels", 
      "bit labels", 
      "simple graph G", 
      "positive integer k", 
      "connected components", 
      "graph G", 
      "integer k", 
      "labeling problem", 
      "same connected component", 
      "Peleg", 
      "optimal solution", 
      "nontrivial solutions", 
      "undirected simple graph G"
    ], 
    "name": "An Optimal Labeling for Node Connectivity", 
    "pagination": "303-310", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008071142"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-10631-6_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-10631-6_32", 
      "https://app.dimensions.ai/details/publication/pub.1008071142"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:38", 
    "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_138.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-10631-6_32"
  }
]
 

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/978-3-642-10631-6_32'

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/978-3-642-10631-6_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_32'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-10631-6_32'


 

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

101 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-10631-6_32 schema:about anzsrc-for:11
2 anzsrc-for:1117
3 schema:author N4860d9fbc3d24f18bc287e0f4b58ac3f
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description Given an n-node undirected simple graph G and a positive integer k, the k-connectivity labeling problem for G seeks short labels for the nodes of G such that whether any two nodes are k-connected in G can be determined merely by their labels. For k = 1, an optimal solution to the problem is to give each node in the same connected component of G a common ⌈log2n⌉-bit label, uniquely chosen for this connected component. For k ≥ 2, Katz, Katz, Korman, and Peleg gave the first nontrivial solution to the problem, requiring O(2klogn) bits per node. The best previously known solution, due to Korman, requires O(k2logn) bits per node. We give the first asymptotically optimal solution to the problem, requiring only \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(2k-1)\left\lceil\log_2 n\right\rceil$\end{document} bits per node, which matches a lower bound Ω(klogn) proved by Katz, Katz, Korman, and Peleg.
7 schema:editor N8415f0026bc3471cbde9933645634f04
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N96cc9d69b692485d902642efdcccf390
12 schema:keywords Katz
13 Korman
14 Peleg
15 bit labels
16 bits
17 components
18 connected components
19 connectivity
20 graph G
21 integer k
22 labeling
23 labeling problem
24 labels
25 node connectivity
26 nodes
27 nontrivial solutions
28 optimal labeling
29 optimal solution
30 positive integer k
31 problem
32 same connected component
33 short labels
34 simple graph G
35 solution
36 undirected simple graph G
37 schema:name An Optimal Labeling for Node Connectivity
38 schema:pagination 303-310
39 schema:productId N25186fcecd5e4f32b18b23c7f689efb7
40 Nfaccd22f71164a7db04d14ffbcc8020a
41 schema:publisher N4471065b961249cdbc438a65cbb39eab
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008071142
43 https://doi.org/10.1007/978-3-642-10631-6_32
44 schema:sdDatePublished 2022-05-10T10:38
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N54a6bf60c9894d6db8e801e1e672737a
47 schema:url https://doi.org/10.1007/978-3-642-10631-6_32
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N09dfe932377a478e9532ae814bfeb4a3 schema:familyName Du
52 schema:givenName Ding-Zhu
53 rdf:type schema:Person
54 N0e1b9c8d7b23477ebbb445e7affb6246 schema:familyName Dong
55 schema:givenName Yingfei
56 rdf:type schema:Person
57 N21b1fa9d3f9d4046b1db94089d9dd99e rdf:first N09dfe932377a478e9532ae814bfeb4a3
58 rdf:rest Nc18d05790ffa471e8d6a9ff2bfaa2d4e
59 N25186fcecd5e4f32b18b23c7f689efb7 schema:name dimensions_id
60 schema:value pub.1008071142
61 rdf:type schema:PropertyValue
62 N4471065b961249cdbc438a65cbb39eab schema:name Springer Nature
63 rdf:type schema:Organisation
64 N4860d9fbc3d24f18bc287e0f4b58ac3f rdf:first N8a395d8fd9a44e598b534b617cddc016
65 rdf:rest N6c6883a987e245b5b5f00e301a1284fb
66 N54a6bf60c9894d6db8e801e1e672737a schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N6c6883a987e245b5b5f00e301a1284fb rdf:first sg:person.013345515575.46
69 rdf:rest rdf:nil
70 N8415f0026bc3471cbde9933645634f04 rdf:first N0e1b9c8d7b23477ebbb445e7affb6246
71 rdf:rest N21b1fa9d3f9d4046b1db94089d9dd99e
72 N8a395d8fd9a44e598b534b617cddc016 schema:affiliation grid-institutes:grid.19188.39
73 schema:familyName Hsu
74 schema:givenName Tai-Hsin
75 rdf:type schema:Person
76 N96cc9d69b692485d902642efdcccf390 schema:isbn 978-3-642-10630-9
77 978-3-642-10631-6
78 schema:name Algorithms and Computation
79 rdf:type schema:Book
80 Nc18d05790ffa471e8d6a9ff2bfaa2d4e rdf:first Nd89c974632414a04aeba1e07bb5daf74
81 rdf:rest rdf:nil
82 Nd89c974632414a04aeba1e07bb5daf74 schema:familyName Ibarra
83 schema:givenName Oscar
84 rdf:type schema:Person
85 Nfaccd22f71164a7db04d14ffbcc8020a schema:name doi
86 schema:value 10.1007/978-3-642-10631-6_32
87 rdf:type schema:PropertyValue
88 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
89 schema:name Medical and Health Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
92 schema:name Public Health and Health Services
93 rdf:type schema:DefinedTerm
94 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
95 schema:familyName Lu
96 schema:givenName Hsueh-I
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
98 rdf:type schema:Person
99 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University
100 schema:name Department of Computer Science and Information Engineering, National Taiwan University
101 rdf:type schema:Organization
 




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


...