2026-07-22T18:55:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16193 2024-03-06T10:57:07Z ddc:004 open_access

Space-Efficient Data Structure for Posets with Applications Yanagita, Tatsuya Chakraborty, Sankardeep Sadakane, Kunihiko Satti, Srinivasa Rao Succinct Data Structures Posets Blockchain Space efficient data structures for partial ordered sets or posets are well-researched field. It is known that a poset with n elements can be represented in n²/4 + o(n²) bits [Munro and Nicholson, 2016] and can also be represented in (1 + ε)n log n + 2nk + o(nk) bits [Farzan and Fischer, 2011] where k is width of the poset. In this paper, we make the latter data structure occupy 2n(k-1) + o(nk) bits by considering topological labeling on the elements of posets. Also considering the topological labeling, we propose a new data structure that calculates queries on transitive reduction graphs of posets faster though queries on transitive closure graphs are computed slower. Moreover, we propose an alternative data structure for topological labeled posets that calculates both of the queries faster though it uses 3nk - 2n + o(nk) bits of space. Additionally, we discuss the advantage of these data structures from the perspective of an application for BlockDAG, which is a more scalable version of Blockchain. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Yanagita and Sankardeep Chakraborty and Kunihiko Sadakane and Srinivasa Rao Satti 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.33 urn:nbn:de:0030-drops-161931 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.33 eng https://creativecommons.org/licenses/by/4.0/legalcode