{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:56Z","timestamp":1767340016787,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation Fellowship","award":["1502650"],"award-info":[{"award-number":["1502650"]}]},{"name":"Fonds de la Recherche Scientifique-FNRS","award":["MISU F 6001 1"],"award-info":[{"award-number":["MISU F 6001 1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s00453-020-00710-w","type":"journal-article","created":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T03:57:30Z","timestamp":1587787050000},"page":"776-794","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Succinct Encodings for Families of Interval Graphs"],"prefix":"10.1007","volume":"83","author":[{"given":"H\u00fcseyin","family":"Acan","sequence":"first","affiliation":[]},{"given":"Sankardeep","family":"Chakraborty","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8644-3691","authenticated-orcid":false,"given":"Seungbum","family":"Jo","sequence":"additional","affiliation":[]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,25]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Acan, H., Chakraborty, S., Jo, S., Satti, S.R.: Succinct data structures for families of interval graphs. In: WADS, pp. 1\u201313 (2019)","key":"710_CR1","DOI":"10.1007\/978-3-030-24766-9_1"},{"issue":"2\u20133","key":"710_CR2","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.tcs.2008.08.016","volume":"408","author":"LC Aleardi","year":"2008","unstructured":"Aleardi, L.C., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci. 408(2\u20133), 174\u2013187 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"710_CR3","doi-asserted-by":"publisher","first-page":"1736","DOI":"10.1007\/s00224-017-9841-2","volume":"62","author":"N Banerjee","year":"2018","unstructured":"Banerjee, N., Chakraborty, S., Raman, V., Satti, S.R.: Space efficient linear time algorithms for BFS, DFS and applications. Theory Comput. Syst. 62(8), 1736\u20131762 (2018)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"710_CR4","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069\u20131090 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"710_CR5","doi-asserted-by":"publisher","first-page":"52:1","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Trans. Algorithms 7(4), 52:1\u201352:27 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"710_CR6","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S Benser","year":"1959","unstructured":"Benser, S.: On the topology of the genetic fine structure. Proc. Natl. Acad. Sci. 45, 1607\u20131620 (1959)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"2","key":"710_CR7","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jagm.1997.0868","volume":"25","author":"BK Bhattacharya","year":"1997","unstructured":"Bhattacharya, B.K., Kaller, D.: An o($$\\text{ m } + \\text{ n } \\log \\text{ n }$$) algorithm for the maximum-clique problem in circular-arc graphs. J. Algorithms 25(2), 336\u2013358 (1997)","journal-title":"J. Algorithms"},{"issue":"3","key":"710_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: WADS, pp. 98\u2013109 (2009). https:\/\/doi.org\/10.1007\/978-3-642-03367-4_9","key":"710_CR9","DOI":"10.1007\/978-3-642-03367-4_9"},{"issue":"4","key":"710_CR10","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"GS Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica 63(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"unstructured":"Chakraborty, S., Grossi, R., Sadakane, K., Satti, S.R.: Succinct representation for (non)deterministic finite automata. CoRR arXiv:abs\/1907.09271 (2019)","key":"710_CR11"},{"doi-asserted-by":"publisher","unstructured":"Chakraborty, S., Mukherjee, A., Raman, V., Satti, S.R.: A framework for in-place graph algorithms. In: ESA, pp. 13:1\u201313:16 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.13","key":"710_CR12","DOI":"10.4230\/LIPIcs.ESA.2018.13"},{"key":"710_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.jcss.2017.06.006","volume":"90","author":"S Chakraborty","year":"2017","unstructured":"Chakraborty, S., Raman, V., Satti, S.R.: Biconnectivity, st-numbering and other applications of DFS using O(n) bits. J. Comput. Syst. Sci. 90, 63\u201379 (2017)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Chakraborty, S., Sadakane, K.: Indexing graph search trees and applications. In: 44th MFCS, pp. 67:1\u201367:14 (2019)","key":"710_CR14"},{"issue":"2","key":"710_CR15","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s10878-018-0270-1","volume":"37","author":"S Chakraborty","year":"2019","unstructured":"Chakraborty, S., Satti, S.R.: Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS. J. Comb. Optim. 37(2), 465\u2013481 (2019)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"710_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1002\/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D","volume":"31","author":"DZ Chen","year":"1998","unstructured":"Chen, D.Z., Lee, D.T., Sridhar, R., Sekharan, C.N.: Solving the all-pair shortest path query problem on interval and circular-arc graphs. Networks 31(4), 249\u2013258 (1998)","journal-title":"Networks"},{"unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: SODA, pp. 383\u2013391 (1996)","key":"710_CR17"},{"key":"710_CR18","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"key":"710_CR19","volume-title":"Graph Theory. Graduate texts in mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate texts in mathematics, vol. 173, 4th edn. Springer, Berlin (2012)","edition":"4"},{"issue":"1","key":"710_CR20","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/s00453-012-9712-9","volume":"69","author":"A Farzan","year":"2014","unstructured":"Farzan, A., Kamali, S.: Compact navigation and distance oracles for graphs with small treewidth. Algorithmica 69(1), 92\u2013116 (2014)","journal-title":"Algorithmica"},{"key":"710_CR21","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2013.09.031","volume":"513","author":"A Farzan","year":"2013","unstructured":"Farzan, A., Munro, J.I.: Succinct encoding of arbitrary graphs. Theor. Comput. Sci. 513, 38\u201352 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"710_CR22","volume-title":"Mathematical Constants","author":"SR Finch","year":"2003","unstructured":"Finch, S.R.: Mathematical Constants. Cambridge University Press, Cambridge (2003)"},{"issue":"2","key":"710_CR23","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"710_CR24","first-page":"216","volume":"1","author":"MR Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Matrix Anal. Appl. 1(2), 216\u2013227 (1980)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"710_CR25","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0012-365X(85)90039-1","volume":"55","author":"MC Golumbic","year":"1985","unstructured":"Golumbic, M.C.: Interval graphs and related topics. Discrete Math. 55(2), 113\u2013121 (1985)","journal-title":"Discrete Math."},{"key":"710_CR26","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"710_CR27","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"MC Golumbic","year":"1988","unstructured":"Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J. Algorithms 9(3), 314\u2013320 (1988)","journal-title":"J. Algorithms"},{"issue":"5","key":"710_CR28","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1145\/174147.169675","volume":"40","author":"MC Golumbic","year":"1993","unstructured":"Golumbic, M.C., Shamir, R.: Complexity and algorithms for reasoning about time: a graph-theoretic approach. J. ACM 40(5), 1108\u20131133 (1993)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: SODA, pp. 368\u2013373 (2006)","key":"710_CR29","DOI":"10.1145\/1109557.1109599"},{"issue":"4","key":"710_CR30","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"UI Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459\u2013467 (1982)","journal-title":"Networks"},{"issue":"1\u20132","key":"710_CR31","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"710_CR32","first-page":"1607","volume":"11","author":"G Haj\u00f3s","year":"1957","unstructured":"Haj\u00f3s, G.: \u00dcber eine art von graphen. Int. Math. Nachr. 11, 1607\u20131620 (1957)","journal-title":"Int. Math. Nachr."},{"issue":"2","key":"710_CR33","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1090\/S0002-9947-1982-0662044-8","volume":"272","author":"P Hanlon","year":"1982","unstructured":"Hanlon, P.: Counting interval graphs. Trans. Am. Math. Soc. 272(2), 383\u2013426 (1982)","journal-title":"Trans. Am. Math. Soc."},{"unstructured":"Klav\u00edk, P., Otachi, Y., Sejnoha, J.: On the classes of interval graphs of limited nesting and count of lengths. In: 27th ISAAC, pp. 45:1\u201345:13 (2016)","key":"710_CR34"},{"issue":"1\u20132","key":"710_CR35","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0012-365X(87)90126-9","volume":"66","author":"S Klavzar","year":"1987","unstructured":"Klavzar, S., Petkovsek, M.: Intersection graphs of halflines and halfplanes. Discrete Math. 66(1\u20132), 133\u2013137 (1987)","journal-title":"Discrete Math."},{"issue":"2","key":"710_CR36","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"RM McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"710_CR37","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2012.03.005","volume":"438","author":"JI Munro","year":"2012","unstructured":"Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations and functions. Theor. Comput. Sci. 438, 74\u201388 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"710_CR38","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Munro, J.I., Wu, K.: Succinct data structures for chordal graphs. In: ISAAC, pp. 67:1\u201367:12 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.67","key":"710_CR39","DOI":"10.4230\/LIPIcs.ISAAC.2018.67"},{"key":"710_CR40","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. J. Discrete Algorithms 25, 2\u201320 (2014)","journal-title":"J. Discrete Algorithms"},{"key":"710_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures\u2014A Practical Approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures\u2014A Practical Approach. Cambridge University Press, Cambridge (2016)"},{"key":"710_CR42","volume-title":"Proof Techniques in Graph Theory","author":"FS Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory. Academic Press, New York (1969)"},{"issue":"1","key":"710_CR43","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"unstructured":"Sloane, N.J.E.: The on-line encyclopedia of integer sequences. http:\/\/oeis.org","key":"710_CR44"},{"issue":"3","key":"710_CR45","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.jcss.2004.04.003","volume":"69","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. 69(3), 330\u2013353 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"710_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/bproc\/27","volume":"4","author":"JC Yang","year":"2017","unstructured":"Yang, J.C., Pippenger, N.: On the enumeration of interval graphs. Proc. Am. Math. Soc. Ser. B 4(1), 1\u20133 (2017)","journal-title":"Proc. Am. Math. Soc. Ser. B"},{"issue":"3","key":"710_CR47","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1093\/bioinformatics\/10.3.309","volume":"10","author":"P Zhang","year":"1994","unstructured":"Zhang, P., Schon, E.A., Cayanis, E., Fischer, S.G., Bourne, P.E., Weiss, J., Kistelr, S.: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Bioinformatics 10(3), 309\u2013317 (1994)","journal-title":"Bioinformatics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00710-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00710-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00710-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T10:23:43Z","timestamp":1619346223000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00710-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,25]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["710"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00710-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,4,25]]},"assertion":[{"value":"19 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}