{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:36:09Z","timestamp":1767339369932,"version":"3.40.5"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Ltd","funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2020R1G1A1101477"],"award-info":[{"award-number":["NRF-2020R1G1A1101477"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MEXT Quantum Leap Flagship Program","award":["JPMXS0120319794"],"award-info":[{"award-number":["JPMXS0120319794"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"abstract":"<jats:p> We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds. <\/jats:p>","DOI":"10.1142\/s012905412341006x","type":"journal-article","created":{"date-parts":[[2023,4,22]],"date-time":"2023-04-22T04:18:29Z","timestamp":1682137109000},"page":"1-18","source":"Crossref","is-referenced-by-count":1,"title":["Succinct Data Structures for SP, Block-Cactus and 3-Leaf Power Graphs"],"prefix":"10.1142","author":[{"given":"Sankardeep","family":"Chakraborty","sequence":"first","affiliation":[{"name":"Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8644-3691","authenticated-orcid":false,"given":"Seungbum","family":"Jo","sequence":"additional","affiliation":[{"name":"The Division of Computer Convergence, Chungnam National University, Daejeon, South Korea"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[{"name":"Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Norwegian University, of Science and Technology, Trondheim, Norway"}]}],"member":"219","published-online":{"date-parts":[[2023,4,21]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412341006X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,22]],"date-time":"2023-04-22T04:18:34Z","timestamp":1682137114000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905412341006X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":0,"alternative-id":["10.1142\/S012905412341006X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412341006x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,4,21]]}}}