Chandoo, M.: Logical Labeling Schemes. Leibniz Universität Hannover, Institut für Theoretische Informatik : Hannover, 2022, 24 S. DOI: http://doi.org/10.15488/11960
Zusammenfassung: | |
A labeling scheme is a space-efficient data structure for encoding graphs from a particular class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can be determined by feeding their labels to an algorithm which returns true iff they are adjacent. For instance, planar and interval graphs have labeling schemes. The label decoding algorithm should be of low complexity since the time it takes to execute corresponds to the time to query an edge. 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 regular labeling schemes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results. | |
Lizenzbestimmungen: | CC BY 3.0 DE |
Publikationstyp: | WorkingPaper |
Publikationsstatus: | submittedVersion |
Erstveröffentlichung: | 2022 |
Die Publikation erscheint in Sammlung(en): | Fakultät für Elektrotechnik und Informatik |
Pos. | Land | Downloads | ||
---|---|---|---|---|
Anzahl | Proz. | |||
1 | Germany | 104 | 57,14% | |
2 | United States | 26 | 14,29% | |
3 | India | 9 | 4,95% | |
4 | United Kingdom | 7 | 3,85% | |
5 | China | 6 | 3,30% | |
6 | No geo information available | 5 | 2,75% | |
7 | Israel | 4 | 2,20% | |
8 | Japan | 3 | 1,65% | |
9 | Malaysia | 2 | 1,10% | |
10 | Denmark | 2 | 1,10% | |
andere | 14 | 7,69% |
Hinweis
Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.