{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:46:57Z","timestamp":1782265617147,"version":"3.54.5"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T00:00:00Z","timestamp":1775692800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T00:00:00Z","timestamp":1775692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["2049010"],"award-info":[{"award-number":["2049010"]}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Zigzag filtrations of simplicial complexes generalize the usual filtrations by allowing simplex deletions in addition to simplex insertions. The barcodes computed from zigzag filtrations encode the evolution of homological features. Although one can locate a particular feature at any index in the filtration using existing algorithms, the resulting\n                    <jats:italic>representatives<\/jats:italic>\n                    may not be compatible with the zigzag: a representative cycle at one index may not map into a representative cycle at its neighbor. For this, one needs to compute compatible representative cycles along each bar in the barcode. It is known that the barcode for a zigzag filtration with\n                    <jats:italic>m<\/jats:italic>\n                    insertions and deletions can be computed in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(m^\\omega )$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mi>\u03c9<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time, where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\omega &lt; 2.373$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03c9<\/mml:mi>\n                            <mml:mo>&lt;<\/mml:mo>\n                            <mml:mn>2.373<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the matrix multiplication exponent. However, it is not known how to compute the compatible representatives so efficiently. For a non-zigzag filtration, the classical matrix-based algorithm provides representatives in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(m^3)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time, which can be improved to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(m^\\omega )$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mi>\u03c9<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . However, no known algorithm for zigzag filtrations computes the representatives with the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(m^3)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time bound. We present an\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(m^2n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time algorithm for this problem, where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n\\le m$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\u2264<\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the size of the largest complex in the filtration.\n                  <\/jats:p>","DOI":"10.1007\/s00453-026-01386-4","type":"journal-article","created":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T01:54:25Z","timestamp":1775699665000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Fast Algorithm for Computing Zigzag Representatives"],"prefix":"10.1007","volume":"88","author":[{"given":"Tamal K.","family":"Dey","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Hou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dmitriy","family":"Morozov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,9]]},"reference":[{"key":"1386_CR1","doi-asserted-by":"crossref","unstructured":"Dey, T.K., Wang, Y.: Computational Topology for Data Analysis, (2022). Cambridge University Press","DOI":"10.1017\/9781009099950"},{"key":"1386_CR2","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction, (2010). American Mathematical Soc","DOI":"10.1090\/mbk\/069"},{"key":"1386_CR3","doi-asserted-by":"crossref","unstructured":"Oudot, S.: Persistence Theory: From Quiver Representations to Data Analysis vol. 209, (2015). AMS Mathematical Surveys and Monographs","DOI":"10.1090\/surv\/209"},{"issue":"1","key":"1386_CR4","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01298413","volume":"6","author":"P Gabriel","year":"1972","unstructured":"Gabriel, P.: Unzerlegbare Darstellungen I. Manuscripta Math. 6(1), 71\u2013103 (1972)","journal-title":"Manuscripta Math."},{"key":"1386_CR5","doi-asserted-by":"crossref","unstructured":"Carlsson, G., Silva, V., Morozov, D.: Zigzag persistent homology and real-valued functions. In: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pp. 247\u2013256 (2009)","DOI":"10.1145\/1542362.1542408"},{"key":"1386_CR6","unstructured":"Dey, T.K., Hou, T.: Fast computation of zigzag persistence. In: 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin\/Potsdam, Germany. LIPIcs, vol. 244, pp. 43\u201314315 (2022). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"1386_CR7","doi-asserted-by":"crossref","unstructured":"Maria, C., Oudot, S.Y.: Zigzag persistence via reflections and transpositions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201915, pp. 181\u2013199. Society for Industrial and Applied Mathematics, USA (2015)","DOI":"10.1137\/1.9781611973730.14"},{"key":"1386_CR8","doi-asserted-by":"crossref","unstructured":"Maria, C., Schreiber, H.: Discrete Morse theory for computing zigzag persistence. In: Algorithms and Data Structures - 16th International Symposium, WADS Proceedings. Lecture Notes in Computer Science, vol. 11646, pp. 538\u2013552 (2019). Springer","DOI":"10.1007\/978-3-030-24766-9_39"},{"key":"1386_CR9","doi-asserted-by":"crossref","unstructured":"Milosavljevi\u0107, N., Morozov, D., Skraba, P.: Zigzag persistent homology in matrix multiplication time. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pp. 216\u2013225 (2011)","DOI":"10.1145\/1998196.1998229"},{"key":"1386_CR10","doi-asserted-by":"crossref","unstructured":"Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pp. 119\u2013126 (2006)","DOI":"10.1145\/1137856.1137877"},{"key":"1386_CR11","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 454\u2013463 (2000). IEEE","DOI":"10.1109\/SFCS.2000.892133"},{"issue":"4","key":"1386_CR12","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10208-010-9066-0","volume":"10","author":"G Carlsson","year":"2010","unstructured":"Carlsson, G., Silva, V.: Zigzag persistence. Found. Comput. Math. 10(4), 367\u2013405 (2010)","journal-title":"Found. Comput. Math."},{"key":"1386_CR13","unstructured":"Dey, T.K., Hou, T.: Computing zigzag persistence on graphs in near-linear time. In: 37th International Symposium on Computational Geometry (2021)"},{"key":"1386_CR14","doi-asserted-by":"crossref","unstructured":"Dey, T.K., Hou, T., Parsa, S.: Revisiting graph persistence for updates and efficiency. In: Algorithms and Data Structures Symposium, pp. 371\u2013385 (2023). Springer","DOI":"10.1007\/978-3-031-38906-1_24"},{"key":"1386_CR15","unstructured":"Dey, T.K., Hou, T.: Computing zigzag vineyard efficiently including expansions and contractions. In: Mulzer, W., Phillips, J.M. (eds.) 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece. LIPIcs, vol. 293, pp. 49\u201314915 (2024)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01386-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01386-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01386-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:10:48Z","timestamp":1782263448000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01386-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,9]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1386"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01386-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,9]]},"assertion":[{"value":"17 September 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"36"}}