Details
| Original language | English |
|---|---|
| Article number | 113565 |
| Journal | Discrete mathematics |
| Volume | 346 |
| Issue number | 10 |
| Early online date | 20 Jun 2023 |
| Publication status | Published - Oct 2023 |
Abstract
A labeling scheme is a space-efficient data structure for encoding graphs from a particular graph class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be algorithmically determined from their labels. For instance, planar and interval graphs have labeling schemes. The algorithm used to determine adjacency—called label decoding algorithm—should be of low complexity since the time it takes to execute corresponds to the time to query an edge in that representation. What graph classes have a labeling scheme if the label decoding algorithm must be very efficient, e.g. computable in constant time? In order to investigate this question we introduce logical labeling schemes where the label decoding algorithm is expressed as a first-order formula and consider their properties such as the relation to labeling schemes defined in terms of classical complexity classes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.
Keywords
- Graph class reduction, Implicit representations, Structural graph theory
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Discrete Mathematics and Combinatorics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Discrete mathematics, Vol. 346, No. 10, 113565, 10.2023.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Logical labeling schemes
AU - Chandoo, Maurice
N1 - Funding Information: I would like to thank Viktor Zamaraev for many stimulating discussions on the subject and for helping me understand the proof behind the refutation of the Implicit Graph Conjecture as well as the anonymous reviewer for giving me valuable feedback to improve the quality of this paper and pointers to relevant results in the literature that I missed.
PY - 2023/10
Y1 - 2023/10
N2 - A labeling scheme is a space-efficient data structure for encoding graphs from a particular graph class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be algorithmically determined from their labels. For instance, planar and interval graphs have labeling schemes. The algorithm used to determine adjacency—called label decoding algorithm—should be of low complexity since the time it takes to execute corresponds to the time to query an edge in that representation. What graph classes have a labeling scheme if the label decoding algorithm must be very efficient, e.g. computable in constant time? In order to investigate this question we introduce logical labeling schemes where the label decoding algorithm is expressed as a first-order formula and consider their properties such as the relation to labeling schemes defined in terms of classical complexity classes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.
AB - A labeling scheme is a space-efficient data structure for encoding graphs from a particular graph class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be algorithmically determined from their labels. For instance, planar and interval graphs have labeling schemes. The algorithm used to determine adjacency—called label decoding algorithm—should be of low complexity since the time it takes to execute corresponds to the time to query an edge in that representation. What graph classes have a labeling scheme if the label decoding algorithm must be very efficient, e.g. computable in constant time? In order to investigate this question we introduce logical labeling schemes where the label decoding algorithm is expressed as a first-order formula and consider their properties such as the relation to labeling schemes defined in terms of classical complexity classes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.
KW - Graph class reduction
KW - Implicit representations
KW - Structural graph theory
UR - http://www.scopus.com/inward/record.url?scp=85162127926&partnerID=8YFLogxK
U2 - 10.15488/11960
DO - 10.15488/11960
M3 - Article
AN - SCOPUS:85162127926
VL - 346
JO - Discrete mathematics
JF - Discrete mathematics
SN - 0012-365X
IS - 10
M1 - 113565
ER -