{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T19:42:46Z","timestamp":1754163766876,"version":"3.41.2"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T00:00:00Z","timestamp":1714089600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T00:00:00Z","timestamp":1714089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018987","name":"Ministerul Cercet\u01cerii, Inovarii \u00e7i Digitaliz\u01cerii","doi-asserted-by":"publisher","award":["PN-III-P1-1.1-TE-2021-0253"],"award-info":[{"award-number":["PN-III-P1-1.1-TE-2021-0253"]}],"id":[{"id":"10.13039\/100018987","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We consider a variant of vertex cover on temporal graphs that has been recently defined for summarization of timeline activities in temporal graphs. The problem has been proved to be NP-hard, even for several restrictions of the time domain and vertex degree. We present novel algorithmic contributions for the problem and we give an approximation algorithm of factor <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(T \\log {n})$$<\/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:mi>T<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, on a temporal graph of <jats:italic>T<\/jats:italic> timestamps and <jats:italic>n<\/jats:italic> vertices. We focus then on the NP-hard restriction of the problem, where at most one temporal edge is defined in each timestamp. For this restriction we present a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$4(T-1)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>T<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution.<\/jats:p>","DOI":"10.1007\/s10479-024-05993-8","type":"journal-article","created":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T02:01:52Z","timestamp":1714096912000},"page":"609-628","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact and approximation algorithms for covering timeline in temporal graphs"],"prefix":"10.1007","volume":"351","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6124-2965","authenticated-orcid":false,"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,26]]},"reference":[{"key":"5993_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., & Makarychev, Y. (2005). O (sqrt log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing (pp. 573\u2013581). https:\/\/doi.org\/10.1145\/1060590.1060675","DOI":"10.1145\/1060590.1060675"},{"key":"5993_CR2","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.jcss.2021.04.001","volume":"120","author":"EC Akrida","year":"2021","unstructured":"Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Raptopoulos, C. L. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, 179\u2013193. https:\/\/doi.org\/10.1016\/j.jcss.2021.04.001","journal-title":"Journal of Computer and System Sciences"},{"key":"5993_CR3","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","volume":"107","author":"EC Akrida","year":"2020","unstructured":"Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108\u2013123. https:\/\/doi.org\/10.1016\/j.jcss.2019.08.002","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"5993_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., & Fujito, T. (1999). A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12(3), 289\u2013297. https:\/\/doi.org\/10.1137\/S0895480196305124","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"5993_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., & Geiger, D. (1996). Optimization of pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83(1), 167\u2013188. https:\/\/doi.org\/10.1016\/0004-3702(95)00004-6","journal-title":"Artificial Intelligence"},{"issue":"3","key":"5993_CR6","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1007\/s00453-022-01018-7","volume":"85","author":"BM Bumpus","year":"2023","unstructured":"Bumpus, B. M., & Meeks, K. (2023). Edge exploration of temporal graphs. Algorithmica, 85(3), 688\u2013716. https:\/\/doi.org\/10.1007\/s00453-022-01018-7","journal-title":"Algorithmica"},{"key":"5993_CR7","doi-asserted-by":"publisher","unstructured":"Dondi, R., & Lafond, M. (2023). An FPT algorithm for temporal graph untangling. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2023.12. Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik","DOI":"10.4230\/LIPICS.IPEC.2023.12"},{"key":"5993_CR8","doi-asserted-by":"publisher","unstructured":"Dondi, R., & Popa, A. (2023). Timeline cover in temporal graphs: Exact and approximation algorithms. In International Workshop on Combinatorial Algorithms (pp. 173\u2013184). https:\/\/doi.org\/10.1007\/978-3-031-34347-6_15","DOI":"10.1007\/978-3-031-34347-6_15"},{"key":"5993_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.114040","volume":"969","author":"R Dondi","year":"2023","unstructured":"Dondi, R. (2023). Untangling temporal graphs of bounded degree. Theoretical Computer Science, 969, 114040. https:\/\/doi.org\/10.1016\/J.TCS.2023.114040","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"5993_CR10","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s42979-021-00593-w","volume":"2","author":"R Dondi","year":"2021","unstructured":"Dondi, R., & Hosseinzadeh, M. M. (2021). Dense sub-networks discovery in temporal networks. SN Computer Science, 2(3), 158. https:\/\/doi.org\/10.1007\/s42979-021-00593-w","journal-title":"SN Computer Science"},{"key":"5993_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2021.01.005","volume":"119","author":"T Erlebach","year":"2021","unstructured":"Erlebach, T., Hoffmann, M., & Kammer, F. (2021). On temporal graph exploration. Journal of Computer and System Sciences, 119, 1\u201318. https:\/\/doi.org\/10.1016\/j.jcss.2021.01.005","journal-title":"Journal of Computer and System Sciences"},{"key":"5993_CR12","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.tcs.2019.03.031","volume":"806","author":"T Fluschnik","year":"2020","unstructured":"Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., & Zschoche, P. (2020). Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806, 197\u2013218. https:\/\/doi.org\/10.1016\/j.tcs.2019.03.031","journal-title":"Theoretical Computer Science"},{"key":"5993_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-023-10150-y","author":"V Froese","year":"2023","unstructured":"Froese, V., Kunz, P., & Zschoche, P. (2023). Disentangling the computational complexity of network untangling. Theory of Computing Systems. https:\/\/doi.org\/10.1007\/s00224-023-10150-y","journal-title":"Theory of Computing Systems"},{"key":"5993_CR14","doi-asserted-by":"publisher","unstructured":"Garg, S., & Philip, G. (2016). Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1152\u20131166). https:\/\/doi.org\/10.1137\/1.9781611974331.CH80","DOI":"10.1137\/1.9781611974331.CH80"},{"key":"5993_CR15","doi-asserted-by":"publisher","unstructured":"Hamm, T., Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2022). The complexity of temporal vertex cover in small-degree graphs. In Proceedings of the AAAI Conference on Artificial Intelligence (vol. 36, pp. 10193\u201310201). https:\/\/doi.org\/10.1609\/aaai.v36i9.21259","DOI":"10.1609\/aaai.v36i9.21259"},{"issue":"3","key":"5993_CR16","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D. S. (1982). Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3), 555\u2013556. https:\/\/doi.org\/10.1137\/0211045","journal-title":"SIAM Journal on Computing"},{"issue":"9","key":"5993_CR17","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"P Holme","year":"2015","unstructured":"Holme, P. (2015). Modern temporal network theory: A colloquium. The European Physical Journal B, 88(9), 234. https:\/\/doi.org\/10.1140\/epjb\/e2015-60657-4","journal-title":"The European Physical Journal B"},{"key":"5993_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23495-9_1","author":"P Holme","year":"2019","unstructured":"Holme, P., & Saram\u00e4ki, J. (2019). A map of approaches to temporal networks. Temporal Network Theory. https:\/\/doi.org\/10.1007\/978-3-030-23495-9_1","journal-title":"Temporal Network Theory"},{"issue":"4","key":"5993_CR19","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G Karakostas","year":"2009","unstructured":"Karakostas, G. (2009). A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms, 5(4), 41\u20131418. https:\/\/doi.org\/10.1145\/1597036.1597045","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"5993_CR20","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J. M., & Kumar, A. (2002). Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4), 820\u2013842. https:\/\/doi.org\/10.1006\/jcss.2002.1829","journal-title":"Journal of Computer and System Sciences"},{"key":"5993_CR21","doi-asserted-by":"publisher","unstructured":"Marino, A., & Silva, A. (2021). K\u00f6nigsberg sightseeing: Eulerian walks in temporal graphs. In International Workshop on Combinatorial Algorithms (pp. 485\u2013500). https:\/\/doi.org\/10.1007\/978-3-030-79987-8_34","DOI":"10.1007\/978-3-030-79987-8_34"},{"issue":"4","key":"5993_CR22","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","volume":"12","author":"O Michail","year":"2016","unstructured":"Michail, O. (2016). An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4), 239\u2013280. https:\/\/doi.org\/10.1080\/15427951.2016.1177801","journal-title":"Internet Mathematics"},{"issue":"4","key":"5993_CR23","doi-asserted-by":"publisher","first-page":"1611","DOI":"10.1007\/s10115-019-01403-9","volume":"62","author":"P Rozenshtein","year":"2020","unstructured":"Rozenshtein, P., Bonchi, F., Gionis, A., Sozio, M., & Tatti, N. (2020). Finding events in temporal networks: Segmentation meets densest subgraph discovery. Knowledge and Information Systems, 62(4), 1611\u20131639. https:\/\/doi.org\/10.1007\/s10115-019-01403-9","journal-title":"Knowledge and Information Systems"},{"issue":"1","key":"5993_CR24","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s10618-020-00717-5","volume":"35","author":"P Rozenshtein","year":"2021","unstructured":"Rozenshtein, P., Tatti, N., & Gionis, A. (2021). The network-untangling problem: From interactions to activity timelines. Data Mining and Knowledge Discovery, 35(1), 213\u2013247. https:\/\/doi.org\/10.1007\/s10618-020-00717-5","journal-title":"Data Mining and Knowledge Discovery"},{"key":"5993_CR25","doi-asserted-by":"publisher","unstructured":"Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., & Xu, Y. (2014). Path problems in temporal graphs. Proceedings of the VLDB Endowment7(9), 721\u2013732 https:\/\/doi.org\/10.14778\/2732939.2732945","DOI":"10.14778\/2732939.2732945"},{"issue":"11","key":"5993_CR26","doi-asserted-by":"publisher","first-page":"2927","DOI":"10.1109\/TKDE.2016.2594065","volume":"28","author":"H Wu","year":"2016","unstructured":"Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., & Wu, H. (2016). Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering, 28(11), 2927\u20132942. https:\/\/doi.org\/10.1109\/TKDE.2016.2594065","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"5993_CR27","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2019.07.006","volume":"107","author":"P Zschoche","year":"2020","unstructured":"Zschoche, P., Fluschnik, T., Molter, H., & Niedermeier, R. (2020). The complexity of finding small separators in temporal graphs. Journal of Computer and System Sciences, 107, 72\u201392. https:\/\/doi.org\/10.1016\/j.jcss.2019.07.006","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-05993-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-024-05993-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-05993-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T13:43:05Z","timestamp":1753969385000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-024-05993-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,26]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["5993"],"URL":"https:\/\/doi.org\/10.1007\/s10479-024-05993-8","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2024,4,26]]},"assertion":[{"value":"25 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2024","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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}