--- _id: '11612' abstract: - lang: eng text: Since the onset of the "space revolution" of high-precision high-cadence photometry, asteroseismology has been demonstrated as a powerful tool for informing Galactic archeology investigations. The launch of the NASA Transiting Exoplanet Survey Satellite (TESS) mission has enabled seismic-based inferences to go full sky—providing a clear advantage for large ensemble studies of the different Milky Way components. Here we demonstrate its potential for investigating the Galaxy by carrying out the first asteroseismic ensemble study of red giant stars observed by TESS. We use a sample of 25 stars for which we measure their global asteroseimic observables and estimate their fundamental stellar properties, such as radius, mass, and age. Significant improvements are seen in the uncertainties of our estimates when combining seismic observables from TESS with astrometric measurements from the Gaia mission compared to when the seismology and astrometry are applied separately. Specifically, when combined we show that stellar radii can be determined to a precision of a few percent, masses to 5%–10%, and ages to the 20% level. This is comparable to the precision typically obtained using end-of-mission Kepler data. acknowledgement: 'This Letter includes data collected by the TESS mission, which are publicly available from the Mikulski Archive for Space Telescopes (MAST). Funding for the TESS mission is provided by NASA''s Science Mission directorate. Funding for the TESS Asteroseismic Science Operations Centre is provided by the Danish National Research Foundation (grant agreement No. DNRF106), ESA PRODEX (PEA 4000119301), and Stellar Astrophysics Centre (SAC) at Aarhus University. V.S.A. acknowledges support from the Independent Research Fund Denmark (Research grant 7027-00096B). D.B. is supported in the form of work contract FCT/MCTES through national funds and by FEDER through COMPETE2020 in connection to these grants: UID/FIS/04434/2019; PTDC/FIS-AST/30389/2017 & POCI-01-0145-FEDER-030389. L.B., R.A.G., and B.M. acknowledge the support from the CNES/PLATO grant. D.B. acknowledges NASA grant NNX16AB76G. T.L.C. acknowledges support from the European Union''s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 792848 (PULSATION). This work was supported by FCT/MCTES through national funds (UID/FIS/04434/2019). E.C. is funded by the European Union''s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No. 664931. R.H. and M.N.L. acknowledge the support of the ESA PRODEX programme. T.S.R. acknowledges financial support from Premiale 2015 MITiC (PI B. Garilli). K.J.B. is supported by the National Science Foundation under Award AST-1903828. M.S.L. is supported by the Carlsberg Foundation (grant agreement No. CF17-0760). M.C. is funded by FCT//MCTES through national funds and by FEDER through COMPETE2020 through these grants: UID/FIS/04434/2019, PTDC/FIS-AST/30389/2017 & POCI-01-0145-FEDER-030389, CEECIND/02619/2017. The research leading to the presented results has received funding from the European Research Council under the European Community''s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 338251 (StellarAges). A.M. acknowledges support from the European Research Council Consolidator Grant funding scheme (project ASTEROCHRONOMETRY, grant agreement No. 772293, http://www.asterochronometry.eu). A.M.S. is partially supported by MINECO grant ESP2017-82674-R. J.C.S. acknowledges funding support from Spanish public funds for research under projects ESP2017-87676-2-2, and from project RYC-2012-09913 under the ''Ramón y Cajal'' program of the Spanish Ministry of Science and Education. Resources supporting this work were provided by the NASA High-End Computing (HEC) Program through the NASA Advanced Supercomputing (NAS) Division at Ames Research Center for the production of the SPOC data products.' article_number: L34 article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Víctor Silva full_name: Aguirre, Víctor Silva last_name: Aguirre - first_name: Dennis full_name: Stello, Dennis last_name: Stello - first_name: Amalie full_name: Stokholm, Amalie last_name: Stokholm - first_name: Jakob R. full_name: Mosumgaard, Jakob R. last_name: Mosumgaard - first_name: Warrick H. full_name: Ball, Warrick H. last_name: Ball - first_name: Sarbani full_name: Basu, Sarbani last_name: Basu - first_name: Diego full_name: Bossini, Diego last_name: Bossini - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 - first_name: Derek full_name: Buzasi, Derek last_name: Buzasi - first_name: Tiago L. full_name: Campante, Tiago L. last_name: Campante - first_name: Lindsey full_name: Carboneau, Lindsey last_name: Carboneau - first_name: William J. full_name: Chaplin, William J. last_name: Chaplin - first_name: Enrico full_name: Corsaro, Enrico last_name: Corsaro - first_name: Guy R. full_name: Davies, Guy R. last_name: Davies - first_name: Yvonne full_name: Elsworth, Yvonne last_name: Elsworth - first_name: Rafael A. full_name: García, Rafael A. last_name: García - first_name: Patrick full_name: Gaulme, Patrick last_name: Gaulme - first_name: Oliver J. full_name: Hall, Oliver J. last_name: Hall - first_name: Rasmus full_name: Handberg, Rasmus last_name: Handberg - first_name: Marc full_name: Hon, Marc last_name: Hon - first_name: Thomas full_name: Kallinger, Thomas last_name: Kallinger - first_name: Liu full_name: Kang, Liu last_name: Kang - first_name: Mikkel N. full_name: Lund, Mikkel N. last_name: Lund - first_name: Savita full_name: Mathur, Savita last_name: Mathur - first_name: Alexey full_name: Mints, Alexey last_name: Mints - first_name: Benoit full_name: Mosser, Benoit last_name: Mosser - first_name: Zeynep full_name: Çelik Orhan, Zeynep last_name: Çelik Orhan - first_name: Thaíse S. full_name: Rodrigues, Thaíse S. last_name: Rodrigues - first_name: Mathieu full_name: Vrard, Mathieu last_name: Vrard - first_name: Mutlu full_name: Yıldız, Mutlu last_name: Yıldız - first_name: Joel C. full_name: Zinn, Joel C. last_name: Zinn - first_name: Sibel full_name: Örtel, Sibel last_name: Örtel - first_name: Paul G. full_name: Beck, Paul G. last_name: Beck - first_name: Keaton J. full_name: Bell, Keaton J. last_name: Bell - first_name: Zhao full_name: Guo, Zhao last_name: Guo - first_name: Chen full_name: Jiang, Chen last_name: Jiang - first_name: James S. full_name: Kuszlewicz, James S. last_name: Kuszlewicz - first_name: Charles A. full_name: Kuehn, Charles A. last_name: Kuehn - first_name: Tanda full_name: Li, Tanda last_name: Li - first_name: Mia S. full_name: Lundkvist, Mia S. last_name: Lundkvist - first_name: Marc full_name: Pinsonneault, Marc last_name: Pinsonneault - first_name: Jamie full_name: Tayar, Jamie last_name: Tayar - first_name: Margarida S. full_name: Cunha, Margarida S. last_name: Cunha - first_name: Saskia full_name: Hekker, Saskia last_name: Hekker - first_name: Daniel full_name: Huber, Daniel last_name: Huber - first_name: Andrea full_name: Miglio, Andrea last_name: Miglio - first_name: Mario J. P. full_name: F. G. Monteiro, Mario J. P. last_name: F. G. Monteiro - first_name: Ditte full_name: Slumstrup, Ditte last_name: Slumstrup - first_name: Mark L. full_name: Winther, Mark L. last_name: Winther - first_name: George full_name: Angelou, George last_name: Angelou - first_name: Othman full_name: Benomar, Othman last_name: Benomar - first_name: Attila full_name: Bódi, Attila last_name: Bódi - first_name: Bruno L. full_name: De Moura, Bruno L. last_name: De Moura - first_name: Sébastien full_name: Deheuvels, Sébastien last_name: Deheuvels - first_name: Aliz full_name: Derekas, Aliz last_name: Derekas - first_name: Maria Pia full_name: Di Mauro, Maria Pia last_name: Di Mauro - first_name: Marc-Antoine full_name: Dupret, Marc-Antoine last_name: Dupret - first_name: Antonio full_name: Jiménez, Antonio last_name: Jiménez - first_name: Yveline full_name: Lebreton, Yveline last_name: Lebreton - first_name: Jaymie full_name: Matthews, Jaymie last_name: Matthews - first_name: Nicolas full_name: Nardetto, Nicolas last_name: Nardetto - first_name: Jose D. full_name: do Nascimento, Jose D. last_name: do Nascimento - first_name: Filipe full_name: Pereira, Filipe last_name: Pereira - first_name: Luisa F. full_name: Rodríguez Díaz, Luisa F. last_name: Rodríguez Díaz - first_name: Aldo M. full_name: Serenelli, Aldo M. last_name: Serenelli - first_name: Emanuele full_name: Spitoni, Emanuele last_name: Spitoni - first_name: Edita full_name: Stonkutė, Edita last_name: Stonkutė - first_name: Juan Carlos full_name: Suárez, Juan Carlos last_name: Suárez - first_name: Robert full_name: Szabó, Robert last_name: Szabó - first_name: Vincent full_name: Van Eylen, Vincent last_name: Van Eylen - first_name: Rita full_name: Ventura, Rita last_name: Ventura - first_name: Kuldeep full_name: Verma, Kuldeep last_name: Verma - first_name: Achim full_name: Weiss, Achim last_name: Weiss - first_name: Tao full_name: Wu, Tao last_name: Wu - first_name: Thomas full_name: Barclay, Thomas last_name: Barclay - first_name: Jørgen full_name: Christensen-Dalsgaard, Jørgen last_name: Christensen-Dalsgaard - first_name: Jon M. full_name: Jenkins, Jon M. last_name: Jenkins - first_name: Hans full_name: Kjeldsen, Hans last_name: Kjeldsen - first_name: George R. full_name: Ricker, George R. last_name: Ricker - first_name: Sara full_name: Seager, Sara last_name: Seager - first_name: Roland full_name: Vanderspek, Roland last_name: Vanderspek citation: ama: 'Aguirre VS, Stello D, Stokholm A, et al. Detection and characterization of oscillating red giants: First results from the TESS satellite. The Astrophysical Journal Letters. 2020;889(2). doi:10.3847/2041-8213/ab6443' apa: 'Aguirre, V. S., Stello, D., Stokholm, A., Mosumgaard, J. R., Ball, W. H., Basu, S., … Vanderspek, R. (2020). Detection and characterization of oscillating red giants: First results from the TESS satellite. The Astrophysical Journal Letters. IOP Publishing. https://doi.org/10.3847/2041-8213/ab6443' chicago: 'Aguirre, Víctor Silva, Dennis Stello, Amalie Stokholm, Jakob R. Mosumgaard, Warrick H. Ball, Sarbani Basu, Diego Bossini, et al. “Detection and Characterization of Oscillating Red Giants: First Results from the TESS Satellite.” The Astrophysical Journal Letters. IOP Publishing, 2020. https://doi.org/10.3847/2041-8213/ab6443.' ieee: 'V. S. Aguirre et al., “Detection and characterization of oscillating red giants: First results from the TESS satellite,” The Astrophysical Journal Letters, vol. 889, no. 2. IOP Publishing, 2020.' ista: 'Aguirre VS, Stello D, Stokholm A, Mosumgaard JR, Ball WH, Basu S, Bossini D, Bugnet LA, Buzasi D, Campante TL, Carboneau L, Chaplin WJ, Corsaro E, Davies GR, Elsworth Y, García RA, Gaulme P, Hall OJ, Handberg R, Hon M, Kallinger T, Kang L, Lund MN, Mathur S, Mints A, Mosser B, Çelik Orhan Z, Rodrigues TS, Vrard M, Yıldız M, Zinn JC, Örtel S, Beck PG, Bell KJ, Guo Z, Jiang C, Kuszlewicz JS, Kuehn CA, Li T, Lundkvist MS, Pinsonneault M, Tayar J, Cunha MS, Hekker S, Huber D, Miglio A, F. G. Monteiro MJP, Slumstrup D, Winther ML, Angelou G, Benomar O, Bódi A, De Moura BL, Deheuvels S, Derekas A, Di Mauro MP, Dupret M-A, Jiménez A, Lebreton Y, Matthews J, Nardetto N, do Nascimento JD, Pereira F, Rodríguez Díaz LF, Serenelli AM, Spitoni E, Stonkutė E, Suárez JC, Szabó R, Van Eylen V, Ventura R, Verma K, Weiss A, Wu T, Barclay T, Christensen-Dalsgaard J, Jenkins JM, Kjeldsen H, Ricker GR, Seager S, Vanderspek R. 2020. Detection and characterization of oscillating red giants: First results from the TESS satellite. The Astrophysical Journal Letters. 889(2), L34.' mla: 'Aguirre, Víctor Silva, et al. “Detection and Characterization of Oscillating Red Giants: First Results from the TESS Satellite.” The Astrophysical Journal Letters, vol. 889, no. 2, L34, IOP Publishing, 2020, doi:10.3847/2041-8213/ab6443.' short: V.S. Aguirre, D. Stello, A. Stokholm, J.R. Mosumgaard, W.H. Ball, S. Basu, D. Bossini, L.A. Bugnet, D. Buzasi, T.L. Campante, L. Carboneau, W.J. Chaplin, E. Corsaro, G.R. Davies, Y. Elsworth, R.A. García, P. Gaulme, O.J. Hall, R. Handberg, M. Hon, T. Kallinger, L. Kang, M.N. Lund, S. Mathur, A. Mints, B. Mosser, Z. Çelik Orhan, T.S. Rodrigues, M. Vrard, M. Yıldız, J.C. Zinn, S. Örtel, P.G. Beck, K.J. Bell, Z. Guo, C. Jiang, J.S. Kuszlewicz, C.A. Kuehn, T. Li, M.S. Lundkvist, M. Pinsonneault, J. Tayar, M.S. Cunha, S. Hekker, D. Huber, A. Miglio, M.J.P. F. G. Monteiro, D. Slumstrup, M.L. Winther, G. Angelou, O. Benomar, A. Bódi, B.L. De Moura, S. Deheuvels, A. Derekas, M.P. Di Mauro, M.-A. Dupret, A. Jiménez, Y. Lebreton, J. Matthews, N. Nardetto, J.D. do Nascimento, F. Pereira, L.F. Rodríguez Díaz, A.M. Serenelli, E. Spitoni, E. Stonkutė, J.C. Suárez, R. Szabó, V. Van Eylen, R. Ventura, K. Verma, A. Weiss, T. Wu, T. Barclay, J. Christensen-Dalsgaard, J.M. Jenkins, H. Kjeldsen, G.R. Ricker, S. Seager, R. Vanderspek, The Astrophysical Journal Letters 889 (2020). date_created: 2022-07-18T13:52:54Z date_published: 2020-02-01T00:00:00Z date_updated: 2022-08-22T07:25:51Z day: '01' doi: 10.3847/2041-8213/ab6443 extern: '1' external_id: arxiv: - '1912.07604' intvolume: ' 889' issue: '2' keyword: - Space and Planetary Science - Astronomy and Astrophysics language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1912.07604 month: '02' oa: 1 oa_version: Preprint publication: The Astrophysical Journal Letters publication_identifier: eissn: - 1538-4357 issn: - 0004-637X publication_status: published publisher: IOP Publishing quality_controlled: '1' scopus_import: '1' status: public title: 'Detection and characterization of oscillating red giants: First results from the TESS satellite' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 889 year: '2020' ... --- _id: '11622' abstract: - lang: eng text: 'The recent discovery of low-amplitude dipolar oscillation mixed modes in massive red giants indicates the presence of a missing physical process inside their cores. Stars more massive than ∼ 1.3 M⊙ are known to develop a convective core during the main-sequence: the dynamo process triggered by this convection could be the origin of a strong magnetic field inside the core of the star, trapped when it becomes stably stratified and for the rest of its evolution. The presence of highly magnetized white dwarfs strengthens the hypothesis of buried fossil magnetic fields inside the core of evolved low-mass stars. If such a fossil field exists, it should affect the mixed modes of red giants as they are sensitive to processes affecting the deepest layers of these stars. The impact of a magnetic field on dipolar oscillations modes was one of Pr. Michael J. Thompson’s research topics during the 90s when preparing the helioseismic SoHO space mission. As the detection of gravity modes in the Sun is still controversial, the investigation of the solar oscillation modes did not provide any hint of the existence of a magnetic field in the solar radiative core. Today we have access to the core of evolved stars thanks to the asteroseismic observation of mixed modes from CoRoT, Kepler, K2 and TESS missions. The idea of applying and generalizing the work done for the Sun came from discussions with Pr. Michael Thompson in early 2018 before we lost him. Following the path we drew together, we theoretically investigate the effect of a stable axisymmetric mixed poloidal and toroidal magnetic field, aligned with the rotation axis of the star, on the mixed modes frequencies of a typical evolved low-mass star. This enables us to estimate the magnetic perturbations to the eigenfrequencies of mixed dipolar modes, depending on the magnetic field strength and the evolutionary state of the star. We conclude that strong magnetic fields of ∼ 1MG should perturb the mixed-mode frequency pattern enough for its effects to be detectable inside current asteroseismic data.' acknowledgement: The authors of this work acknowledge the support received from the PLATO CNES grant, the National Aeronautics and Space Administration under Grant NNX15AF13G, by the National Science Foundation grant AST-1411685, the Ramon y Cajal fellowship number RYC-2015-17697, the ERC SPIRE grant (647383), and the Fundation L’Oréal-Unesco-Académie des sciences. alternative_title: - Astrophysics and Space Science Proceedings article_processing_charge: No arxiv: 1 author: - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 - first_name: V. full_name: Prat, V. last_name: Prat - first_name: S. full_name: Mathis, S. last_name: Mathis - first_name: R. A. full_name: García, R. A. last_name: García - first_name: S. full_name: Mathur, S. last_name: Mathur - first_name: K. full_name: Augustson, K. last_name: Augustson - first_name: C. full_name: Neiner, C. last_name: Neiner - first_name: M. J. full_name: Thompson, M. J. last_name: Thompson citation: ama: 'Bugnet LA, Prat V, Mathis S, et al. The impact of a fossil magnetic field on dipolar mixed-mode frequencies in sub- and red-giant stars. In: Monteiro M, Garcia RA, Christensen-Dalsgaard J, McIntosh SW, eds. Dynamics of the Sun and Stars. Vol 57. 1st ed. ASSSP. Cham: Springer Nature; 2020:251-257. doi:10.1007/978-3-030-55336-4_33' apa: 'Bugnet, L. A., Prat, V., Mathis, S., García, R. A., Mathur, S., Augustson, K., … Thompson, M. J. (2020). The impact of a fossil magnetic field on dipolar mixed-mode frequencies in sub- and red-giant stars. In M. Monteiro, R. A. Garcia, J. Christensen-Dalsgaard, & S. W. McIntosh (Eds.), Dynamics of the Sun and Stars (1st ed., Vol. 57, pp. 251–257). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-55336-4_33' chicago: 'Bugnet, Lisa Annabelle, V. Prat, S. Mathis, R. A. García, S. Mathur, K. Augustson, C. Neiner, and M. J. Thompson. “The Impact of a Fossil Magnetic Field on Dipolar Mixed-Mode Frequencies in Sub- and Red-Giant Stars.” In Dynamics of the Sun and Stars, edited by Mario Monteiro, Rafael A Garcia, Jorgen Christensen-Dalsgaard, and Scott W McIntosh, 1st ed., 57:251–57. ASSSP. Cham: Springer Nature, 2020. https://doi.org/10.1007/978-3-030-55336-4_33.' ieee: 'L. A. Bugnet et al., “The impact of a fossil magnetic field on dipolar mixed-mode frequencies in sub- and red-giant stars,” in Dynamics of the Sun and Stars, 1st ed., vol. 57, M. Monteiro, R. A. Garcia, J. Christensen-Dalsgaard, and S. W. McIntosh, Eds. Cham: Springer Nature, 2020, pp. 251–257.' ista: 'Bugnet LA, Prat V, Mathis S, García RA, Mathur S, Augustson K, Neiner C, Thompson MJ. 2020.The impact of a fossil magnetic field on dipolar mixed-mode frequencies in sub- and red-giant stars. In: Dynamics of the Sun and Stars. Astrophysics and Space Science Proceedings, vol. 57, 251–257.' mla: Bugnet, Lisa Annabelle, et al. “The Impact of a Fossil Magnetic Field on Dipolar Mixed-Mode Frequencies in Sub- and Red-Giant Stars.” Dynamics of the Sun and Stars, edited by Mario Monteiro et al., 1st ed., vol. 57, Springer Nature, 2020, pp. 251–57, doi:10.1007/978-3-030-55336-4_33. short: L.A. Bugnet, V. Prat, S. Mathis, R.A. García, S. Mathur, K. Augustson, C. Neiner, M.J. Thompson, in:, M. Monteiro, R.A. Garcia, J. Christensen-Dalsgaard, S.W. McIntosh (Eds.), Dynamics of the Sun and Stars, 1st ed., Springer Nature, Cham, 2020, pp. 251–257. date_created: 2022-07-19T08:25:41Z date_published: 2020-12-19T00:00:00Z date_updated: 2024-10-14T11:42:19Z day: '19' doi: 10.1007/978-3-030-55336-4_33 edition: '1' editor: - first_name: Mario full_name: Monteiro, Mario last_name: Monteiro - first_name: Rafael A full_name: Garcia, Rafael A last_name: Garcia - first_name: Jorgen full_name: Christensen-Dalsgaard, Jorgen last_name: Christensen-Dalsgaard - first_name: Scott W full_name: McIntosh, Scott W last_name: McIntosh extern: '1' external_id: arxiv: - '2012.08684' intvolume: ' 57' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2012.08684 month: '12' oa: 1 oa_version: Preprint page: 251-257 place: Cham publication: Dynamics of the Sun and Stars publication_identifier: eisbn: - 978-3-030-55336-4 eissn: - 1570-6605 isbn: - 978-3-030-55335-7 issn: - 1570-6591 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: ASSSP status: public title: The impact of a fossil magnetic field on dipolar mixed-mode frequencies in sub- and red-giant stars type: book_chapter user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 57 year: '2020' ... --- _id: '11674' abstract: - lang: eng text: In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem. article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Dariusz full_name: Leniowski, Dariusz last_name: Leniowski - first_name: Claire full_name: Mathieu, Claire last_name: Mathieu citation: ama: Henzinger M, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. Algorithmica. 2020;82(11):3183-3194. doi:10.1007/s00453-020-00721-7 apa: Henzinger, M., Leniowski, D., & Mathieu, C. (2020). Dynamic clustering to minimize the sum of radii. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-020-00721-7 chicago: Henzinger, Monika, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-020-00721-7. ieee: M. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” Algorithmica, vol. 82, no. 11. Springer Nature, pp. 3183–3194, 2020. ista: Henzinger M, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194. mla: Henzinger, Monika, et al. “Dynamic Clustering to Minimize the Sum of Radii.” Algorithmica, vol. 82, no. 11, Springer Nature, 2020, pp. 3183–94, doi:10.1007/s00453-020-00721-7. short: M. Henzinger, D. Leniowski, C. Mathieu, Algorithmica 82 (2020) 3183–3194. date_created: 2022-07-27T13:58:58Z date_published: 2020-11-01T00:00:00Z date_updated: 2024-11-04T11:41:57Z day: '01' doi: 10.1007/s00453-020-00721-7 extern: '1' external_id: arxiv: - '1707.02577' intvolume: ' 82' issue: '11' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.1707.02577 month: '11' oa: 1 oa_version: Preprint page: 3183-3194 publication: Algorithmica publication_identifier: eissn: - 1432-0541 issn: - 0178-4617 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Dynamic clustering to minimize the sum of radii type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 82 year: '2020' ... --- _id: '11675' abstract: - lang: eng text: 'We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.' article_processing_charge: No article_type: original author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Deeparnab full_name: Chakrabarty, Deeparnab last_name: Chakrabarty - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching in O(1) update time. Algorithmica. 2020;82(4):1057-1080. doi:10.1007/s00453-019-00630-4 apa: Bhattacharya, S., Chakrabarty, D., & Henzinger, M. (2020). Deterministic dynamic matching in O(1) update time. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-019-00630-4 chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-019-00630-4. ieee: S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic matching in O(1) update time,” Algorithmica, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020. ista: Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080. mla: Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update Time.” Algorithmica, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80, doi:10.1007/s00453-019-00630-4. short: S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080. date_created: 2022-07-27T14:31:06Z date_published: 2020-04-01T00:00:00Z date_updated: 2024-11-06T12:07:43Z day: '01' doi: 10.1007/s00453-019-00630-4 extern: '1' intvolume: ' 82' issue: '4' keyword: - Dynamic algorithms - Data structures - Graph algorithms - Matching - Vertex cover language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1007/s00453-019-00630-4 month: '04' oa: 1 oa_version: Published Version page: 1057-1080 publication: Algorithmica publication_identifier: eissn: - 1432-0541 issn: - 0178-4617 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Deterministic dynamic matching in O(1) update time type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 82 year: '2020' ... --- _id: '11816' abstract: - lang: eng text: In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances. alternative_title: - LIPIcs article_number: '58' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Khan full_name: Shahbaz, Khan last_name: Shahbaz - first_name: Richard full_name: Paul, Richard last_name: Paul - first_name: Christian full_name: Schulz, Christian last_name: Schulz citation: ama: 'Henzinger M, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: 8th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.58' apa: 'Henzinger, M., Shahbaz, K., Paul, R., & Schulz, C. (2020). Dynamic matching algorithms in practice. In 8th Annual European Symposium on Algorithms (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.58' chicago: Henzinger, Monika, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In 8th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.58. ieee: M. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in 8th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173. ista: 'Henzinger M, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.' mla: Henzinger, Monika, et al. “Dynamic Matching Algorithms in Practice.” 8th Annual European Symposium on Algorithms, vol. 173, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.ESA.2020.58. short: M. Henzinger, K. Shahbaz, R. Paul, C. Schulz, in:, 8th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-09-09 location: Pisa, Italy name: 'ESA: Annual European Symposium on Algorithms' start_date: 2020-09-07 date_created: 2022-08-12T07:13:25Z date_published: 2020-08-26T00:00:00Z date_updated: 2024-11-06T08:23:03Z day: '26' doi: 10.4230/LIPIcs.ESA.2020.58 extern: '1' external_id: arxiv: - '2004.09099' intvolume: ' 173' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2020.58 month: '08' oa: 1 oa_version: Published Version publication: 8th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959771627' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Dynamic matching algorithms in practice type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 173 year: '2020' ... --- _id: '11818' abstract: - lang: eng text: "With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive.\r\nAs a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space.\r\nWe also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant." alternative_title: - LIPIcs article_number: '57' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sagar full_name: Kale, Sagar last_name: Kale citation: ama: 'Henzinger M, Kale S. Fully-dynamic coresets. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.57' apa: 'Henzinger, M., & Kale, S. (2020). Fully-dynamic coresets. In 28th Annual European Symposium on Algorithms (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.57' chicago: Henzinger, Monika, and Sagar Kale. “Fully-Dynamic Coresets.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.57. ieee: M. Henzinger and S. Kale, “Fully-dynamic coresets,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173. ista: 'Henzinger M, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.' mla: Henzinger, Monika, and Sagar Kale. “Fully-Dynamic Coresets.” 28th Annual European Symposium on Algorithms, vol. 173, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.ESA.2020.57. short: M. Henzinger, S. Kale, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-09-09 location: Pisa, Italy name: 'ESA: Annual European Symposium on Algorithms' start_date: 2020-09-07 date_created: 2022-08-12T07:22:55Z date_published: 2020-08-26T00:00:00Z date_updated: 2024-11-06T08:22:13Z day: '26' doi: 10.4230/LIPIcs.ESA.2020.57 extern: '1' external_id: arxiv: - '2004.14891' intvolume: ' 173' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2020.57 month: '08' oa: 1 oa_version: Published Version publication: 28th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959771627' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Fully-dynamic coresets type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 173 year: '2020' ... --- _id: '11819' abstract: - lang: eng text: We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts. alternative_title: - LIPIcs article_number: '59' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Alexander full_name: Noe, Alexander last_name: Noe - first_name: Christian full_name: Schulz, Christian last_name: Schulz - first_name: Darren full_name: Strash, Darren last_name: Strash citation: ama: 'Henzinger M, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: 28th Annual European Symposium on Algorithms. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.ESA.2020.59' apa: 'Henzinger, M., Noe, A., Schulz, C., & Strash, D. (2020). Finding all global minimum cuts in practice. In 28th Annual European Symposium on Algorithms (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2020.59' chicago: Henzinger, Monika, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In 28th Annual European Symposium on Algorithms, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.59. ieee: M. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173. ista: 'Henzinger M, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.' mla: Henzinger, Monika, et al. “Finding All Global Minimum Cuts in Practice.” 28th Annual European Symposium on Algorithms, vol. 173, 59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.ESA.2020.59. short: M. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-09-09 location: Pisa, Italy name: 'ESA: Annual European Symposium on Algorithms' start_date: 2020-09-07 date_created: 2022-08-12T07:27:42Z date_published: 2020-08-26T00:00:00Z date_updated: 2024-11-06T08:23:16Z day: '26' doi: 10.4230/LIPIcs.ESA.2020.59 extern: '1' external_id: arxiv: - '2002.06948' intvolume: ' 173' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2020.59 month: '08' oa: 1 oa_version: Published Version publication: 28th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959771627' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Finding all global minimum cuts in practice type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 173 year: '2020' ... --- _id: '11822' abstract: - lang: eng text: "The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.\r\nIn this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice." alternative_title: - LIPIcs article_number: '14' article_processing_charge: No arxiv: 1 author: - first_name: Kathrin full_name: Hanauer, Kathrin last_name: Hanauer - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Christian full_name: Schulz, Christian last_name: Schulz citation: ama: 'Hanauer K, Henzinger M, Schulz C. Faster fully dynamic transitive closure in practice. In: 18th International Symposium on Experimental Algorithms. Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SEA.2020.14' apa: 'Hanauer, K., Henzinger, M., & Schulz, C. (2020). Faster fully dynamic transitive closure in practice. In 18th International Symposium on Experimental Algorithms (Vol. 160). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SEA.2020.14' chicago: Hanauer, Kathrin, Monika Henzinger, and Christian Schulz. “Faster Fully Dynamic Transitive Closure in Practice.” In 18th International Symposium on Experimental Algorithms, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SEA.2020.14. ieee: K. Hanauer, M. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” in 18th International Symposium on Experimental Algorithms, Pisa, Italy, 2020, vol. 160. ista: 'Hanauer K, Henzinger M, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.' mla: Hanauer, Kathrin, et al. “Faster Fully Dynamic Transitive Closure in Practice.” 18th International Symposium on Experimental Algorithms, vol. 160, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SEA.2020.14. short: K. Hanauer, M. Henzinger, C. Schulz, in:, 18th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-09-09 location: Pisa, Italy name: 'SEA: Symposium on Experimental Algorithms' start_date: 2020-09-07 date_created: 2022-08-12T07:32:53Z date_published: 2020-06-12T00:00:00Z date_updated: 2024-11-06T11:57:02Z day: '12' doi: 10.4230/LIPIcs.SEA.2020.14 extern: '1' external_id: arxiv: - '2002.00813' intvolume: ' 160' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.SEA.2020.14 month: '06' oa: 1 oa_version: Published Version publication: 18th International Symposium on Experimental Algorithms publication_identifier: isbn: - '9783959771481' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Faster fully dynamic transitive closure in practice type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 160 year: '2020' ... --- _id: '11824' abstract: - lang: eng text: "Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect.\r\nWe present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:\r\n- For weighted intervals, we maintain a (1+ε)-approximate solution.\r\n- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds.\r\n- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N." alternative_title: - LIPIcs article_number: '51' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Stefan full_name: Neumann, Stefan last_name: Neumann - first_name: Andreas full_name: Wiese, Andreas last_name: Wiese citation: ama: 'Henzinger M, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.51' apa: 'Henzinger, M., Neumann, S., & Wiese, A. (2020). Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In 36th International Symposium on Computational Geometry (Vol. 164). Zurich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.51' chicago: Henzinger, Monika, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.51. ieee: M. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in 36th International Symposium on Computational Geometry, Zurich, Switzerland, 2020, vol. 164. ista: 'Henzinger M, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.' mla: Henzinger, Monika, et al. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” 36th International Symposium on Computational Geometry, vol. 164, 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.51. short: M. Henzinger, S. Neumann, A. Wiese, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-06-26 location: Zurich, Switzerland name: 'SoCG: Symposium on Computational Geometry' start_date: 2020-06-23 date_created: 2022-08-12T07:46:44Z date_published: 2020-06-08T00:00:00Z date_updated: 2024-11-06T11:56:49Z day: '08' doi: 10.4230/LIPIcs.SoCG.2020.51 extern: '1' external_id: arxiv: - '2003.02605' intvolume: ' 164' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.SoCG.2020.51 month: '06' oa: 1 oa_version: Published Version publication: 36th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959771436' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 164 year: '2020' ... --- _id: '11825' abstract: - lang: eng text: We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation. alternative_title: - LIPIcs article_number: '53' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Pan full_name: Peng, Pan last_name: Peng citation: ama: 'Henzinger M, Peng P. Constant-time dynamic (Δ+1)-coloring. In: 37th International Symposium on Theoretical Aspects of Computer Science. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.STACS.2020.53' apa: 'Henzinger, M., & Peng, P. (2020). Constant-time dynamic (Δ+1)-coloring. In 37th International Symposium on Theoretical Aspects of Computer Science (Vol. 154). Montpellier, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2020.53' chicago: Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In 37th International Symposium on Theoretical Aspects of Computer Science, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.STACS.2020.53. ieee: M. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France, 2020, vol. 154. ista: 'Henzinger M, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.' mla: Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” 37th International Symposium on Theoretical Aspects of Computer Science, vol. 154, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.STACS.2020.53. short: M. Henzinger, P. Peng, in:, 37th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. conference: end_date: 2020-03-13 location: Montpellier, France name: 'STACS: Symposium on Theoretical Aspects of Computer Science' start_date: 2020-03-10 date_created: 2022-08-12T07:53:05Z date_published: 2020-03-04T00:00:00Z date_updated: 2024-11-06T11:57:29Z day: '04' doi: 10.4230/LIPIcs.STACS.2020.53 extern: '1' external_id: arxiv: - '1907.04745' intvolume: ' 154' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.STACS.2020.53 month: '03' oa: 1 oa_version: Published Version publication: 37th International Symposium on Theoretical Aspects of Computer Science publication_identifier: isbn: - '9783959771405' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Constant-time dynamic (Δ+1)-coloring type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 154 year: '2020' ... --- _id: '11852' abstract: - lang: eng text: We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in O~(n2/3) 11The O~(⋅) notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and O~(m3/4) time against an adaptive adversary. (2)An incremental data structure that maintains O(1) - approximate shortest path in no(1) time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in O~(n2/3+o(1)) amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an (1+ϵ) factor in O~(n2/3+o(1)ϵ−O(1)) amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The O(1)-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https://arxiv.org/pdf/2005.02368.pdf for the full version of this paper. article_processing_charge: No arxiv: 1 author: - first_name: Li full_name: Chen, Li last_name: Chen - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Richard full_name: Peng, Richard last_name: Peng - first_name: Thatchaphol full_name: Saranurak, Thatchaphol last_name: Saranurak citation: ama: 'Chen L, Goranci G, Henzinger M, Peng R, Saranurak T. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: 61st Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2020:1135-1146. doi:10.1109/focs46700.2020.00109' apa: 'Chen, L., Goranci, G., Henzinger, M., Peng, R., & Saranurak, T. (2020). Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In 61st Annual Symposium on Foundations of Computer Science (pp. 1135–1146). Durham, NC, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs46700.2020.00109' chicago: Chen, Li, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” In 61st Annual Symposium on Foundations of Computer Science, 1135–46. Institute of Electrical and Electronics Engineers, 2020. https://doi.org/10.1109/focs46700.2020.00109. ieee: L. Chen, G. Goranci, M. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic cuts, distances and effective resistances via vertex sparsifiers,” in 61st Annual Symposium on Foundations of Computer Science, Durham, NC, United States, 2020, pp. 1135–1146. ista: 'Chen L, Goranci G, Henzinger M, Peng R, Saranurak T. 2020. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. 61st Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 1135–1146.' mla: Chen, Li, et al. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” 61st Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–46, doi:10.1109/focs46700.2020.00109. short: L. Chen, G. Goranci, M. Henzinger, R. Peng, T. Saranurak, in:, 61st Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–1146. conference: end_date: 2020-11-19 location: Durham, NC, United States name: 'FOCS: Annual Symposium on Foundations of Computer Science' start_date: 2020-11-16 date_created: 2022-08-16T07:33:12Z date_published: 2020-11-01T00:00:00Z date_updated: 2024-11-06T12:17:53Z day: '01' doi: 10.1109/focs46700.2020.00109 extern: '1' external_id: arxiv: - '2005.02368' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2005.02368 month: '11' oa: 1 oa_version: Preprint page: 1135-1146 publication: 61st Annual Symposium on Foundations of Computer Science publication_identifier: eisbn: - 978-1-7281-9621-3 eissn: - 2575-8454 isbn: - 978-1-7281-9622-0 publication_status: published publisher: Institute of Electrical and Electronics Engineers quality_controlled: '1' scopus_import: '1' status: public title: Fast dynamic cuts, distances and effective resistances via vertex sparsifiers type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '11880' abstract: - lang: eng text: "Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subject to edge deletions and insertions. It is one of the most fundamental problems on graphs and appears directly or indirectly in many and varied applications. While there has been theoretical work on this problem, showing both linear conditional lower bounds for the fully dynamic problem and insertions-only and deletions-only upper bounds beating these conditional lower bounds, there has been no experimental study that compares the performance of fully dynamic reachability algorithms in practice. Previous experimental studies in this area concentrated only on the more general all-pairs reachability or transitive closure problem and did not use real-world dynamic graphs.\r\n\r\nIn this paper, we bridge this gap by empirically studying an extensive set of algorithms for the single-source reachability problem in the fully dynamic setting. In particular, we design several fully dynamic variants of well-known approaches to obtain and maintain reachability information with respect to a distinguished source. Moreover, we extend the existing insertions-only or deletions-only upper bounds into fully dynamic algorithms. Even though the worst-case time per operation of all the fully dynamic algorithms we evaluate is at least linear in the number of edges in the graph (as is to be expected given the conditional lower bounds) we show in our extensive experimental evaluation that their performance differs greatly, both on generated as well as on real-world instances." article_processing_charge: No arxiv: 1 author: - first_name: Kathrin full_name: Hanauer, Kathrin last_name: Hanauer - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Christian full_name: Schulz, Christian last_name: Schulz citation: ama: 'Hanauer K, Henzinger M, Schulz C. Fully dynamic single-source reachability in practice: An experimental study. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:106-119. doi:10.1137/1.9781611976007.9' apa: 'Hanauer, K., Henzinger, M., & Schulz, C. (2020). Fully dynamic single-source reachability in practice: An experimental study. In 2020 Symposium on Algorithm Engineering and Experiments (pp. 106–119). Salt Lake City, UT, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976007.9' chicago: 'Hanauer, Kathrin, Monika Henzinger, and Christian Schulz. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” In 2020 Symposium on Algorithm Engineering and Experiments, 106–19. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.9.' ieee: 'K. Hanauer, M. Henzinger, and C. Schulz, “Fully dynamic single-source reachability in practice: An experimental study,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 106–119.' ista: 'Hanauer K, Henzinger M, Schulz C. 2020. Fully dynamic single-source reachability in practice: An experimental study. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 106–119.' mla: 'Hanauer, Kathrin, et al. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 106–19, doi:10.1137/1.9781611976007.9.' short: K. Hanauer, M. Henzinger, C. Schulz, in:, 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 106–119. conference: end_date: 2020-01-06 location: Salt Lake City, UT, United States name: 'ALENEX: Symposium on Algorithm Engineering and Experiments' start_date: 2020-01-05 date_created: 2022-08-17T06:39:32Z date_published: 2020-01-01T00:00:00Z date_updated: 2024-11-06T12:21:47Z day: '01' doi: 10.1137/1.9781611976007.9 extern: '1' external_id: arxiv: - '1905.01216' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1905.01216 month: '01' oa: 1 oa_version: Preprint page: 106-119 publication: 2020 Symposium on Algorithm Engineering and Experiments publication_identifier: eisbn: - 978-1-61197-600-7 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: 'Fully dynamic single-source reachability in practice: An experimental study' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '11881' abstract: - lang: eng text: We introduce the fastest known exact algorithm for the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible. article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Alexander full_name: Noe, Alexander last_name: Noe - first_name: Christian full_name: Schulz, Christian last_name: Schulz citation: ama: 'Henzinger M, Noe A, Schulz C. Shared-memory branch-and-reduce for multiterminal cuts. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:42-55. doi:10.1137/1.9781611976007.4' apa: 'Henzinger, M., Noe, A., & Schulz, C. (2020). Shared-memory branch-and-reduce for multiterminal cuts. In 2020 Symposium on Algorithm Engineering and Experiments (pp. 42–55). Salt Lake City, UT, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976007.4' chicago: Henzinger, Monika, Alexander Noe, and Christian Schulz. “Shared-Memory Branch-and-Reduce for Multiterminal Cuts.” In 2020 Symposium on Algorithm Engineering and Experiments, 42–55. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.4. ieee: M. Henzinger, A. Noe, and C. Schulz, “Shared-memory branch-and-reduce for multiterminal cuts,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 42–55. ista: 'Henzinger M, Noe A, Schulz C. 2020. Shared-memory branch-and-reduce for multiterminal cuts. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 42–55.' mla: Henzinger, Monika, et al. “Shared-Memory Branch-and-Reduce for Multiterminal Cuts.” 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 42–55, doi:10.1137/1.9781611976007.4. short: M. Henzinger, A. Noe, C. Schulz, in:, 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 42–55. conference: end_date: 2020-01-06 location: Salt Lake City, UT, United States name: 'ALENEX: Symposium on Algorithm Engineering and Experiments' start_date: 2020-01-05 date_created: 2022-08-17T06:47:40Z date_published: 2020-01-01T00:00:00Z date_updated: 2024-11-06T12:21:58Z day: '01' doi: 10.1137/1.9781611976007.4 extern: '1' external_id: arxiv: - '1908.04141' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1908.04141 month: '01' oa: 1 oa_version: Preprint page: 42-55 publication: 2020 Symposium on Algorithm Engineering and Experiments publication_identifier: eisbn: - 978-1-61197-600-7 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: Shared-memory branch-and-reduce for multiterminal cuts type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2020' ... --- _id: '11889' abstract: - lang: eng text: "We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic \U0001D442(\U0001D45Alog2\U0001D45Bloglog2\U0001D45B) time algorithm. This improves on both the best previously known deterministic running time of \U0001D442(\U0001D45Alog12\U0001D45B) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 4]) and the best previously known randomized running time of \U0001D442(\U0001D45Alog3\U0001D45B) (Karger [J. ACM, 47 (2000), pp. 46--76]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow- and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest." article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Satish full_name: Rao, Satish last_name: Rao - first_name: Di full_name: Wang, Di last_name: Wang citation: ama: Henzinger M, Rao S, Wang D. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 2020;49(1):1-36. doi:10.1137/18m1180335 apa: Henzinger, M., Rao, S., & Wang, D. (2020). Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/18m1180335 chicago: Henzinger, Monika, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/18m1180335. ieee: M. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” SIAM Journal on Computing, vol. 49, no. 1. Society for Industrial & Applied Mathematics, pp. 1–36, 2020. ista: Henzinger M, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36. mla: Henzinger, Monika, et al. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing, vol. 49, no. 1, Society for Industrial & Applied Mathematics, 2020, pp. 1–36, doi:10.1137/18m1180335. short: M. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36. date_created: 2022-08-17T08:09:31Z date_published: 2020-01-01T00:00:00Z date_updated: 2024-11-06T12:22:42Z day: '01' doi: 10.1137/18m1180335 extern: '1' external_id: arxiv: - '1704.01254' intvolume: ' 49' issue: '1' language: - iso: eng main_file_link: - url: https://arxiv.org/abs/1704.01254 month: '01' oa_version: Preprint page: 1-36 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: Society for Industrial & Applied Mathematics quality_controlled: '1' related_material: record: - id: '11873' relation: later_version status: public scopus_import: '1' status: public title: Local flow partitioning for faster edge connectivity type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 49 year: '2020' ... --- _id: '11894' abstract: - lang: eng text: "Graph sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the input graph. In this work we study vertex sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. We focus on the following notions: (1) Given a digraph \U0001D43A=(\U0001D449,\U0001D438) and terminal vertices \U0001D43E⊂\U0001D449 with |\U0001D43E|=\U0001D458, a (vertex) reachability sparsifier of \U0001D43A is a digraph \U0001D43B=(\U0001D449\U0001D43B,\U0001D438\U0001D43B), \U0001D43E⊂\U0001D449\U0001D43B that preserves all reachability information among terminal pairs. Let |\U0001D449\U0001D43B| denote the size of \U0001D43B. In this work we introduce the notion of reachability-preserving minors (RPMs), i.e., we require \U0001D43B to be a minor of \U0001D43A. We show any directed graph \U0001D43A admits an RPM \U0001D43B of size \U0001D442(\U0001D4583), and if \U0001D43A is planar, then the size of \U0001D43B improves to \U0001D442(\U0001D4582log\U0001D458). We complement our upper bound by showing that there exists an infinite family of grids such that any RPM must have Ω(\U0001D4582) vertices. (2) Given a weighted undirected graph \U0001D43A=(\U0001D449,\U0001D438) and terminal vertices \U0001D43E with |\U0001D43E|=\U0001D458, an exact (vertex) cut sparsifier of \U0001D43A is a graph \U0001D43B with \U0001D43E⊂\U0001D449\U0001D43B that preserves the value of minimum cuts separating any bipartition of \U0001D43E. We show that planar graphs with all the \U0001D458 terminals lying on the same face admit exact cut sparsifiers of size \U0001D442(\U0001D4582) that are also planar. Our result extends to flow and distance sparsifiers. It improves the previous best-known bound of \U0001D442(\U0001D458222\U0001D458) for cut and flow sparsifiers by an exponential factor and matches an Ω(\U0001D4582) lower-bound for this class of graphs." article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Pan full_name: Peng, Pan last_name: Peng citation: ama: Goranci G, Henzinger M, Peng P. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 2020;34(1):130-162. doi:10.1137/17m1163153 apa: Goranci, G., Henzinger, M., & Peng, P. (2020). Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/17m1163153 chicago: Goranci, Gramoz, Monika Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/17m1163153. ieee: G. Goranci, M. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” SIAM Journal on Discrete Mathematics, vol. 34, no. 1. Society for Industrial & Applied Mathematics, pp. 130–162, 2020. ista: Goranci G, Henzinger M, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162. mla: Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” SIAM Journal on Discrete Mathematics, vol. 34, no. 1, Society for Industrial & Applied Mathematics, 2020, pp. 130–62, doi:10.1137/17m1163153. short: G. Goranci, M. Henzinger, P. Peng, SIAM Journal on Discrete Mathematics 34 (2020) 130–162. date_created: 2022-08-17T08:50:24Z date_published: 2020-01-01T00:00:00Z date_updated: 2024-11-06T11:57:54Z day: '01' doi: 10.1137/17m1163153 extern: '1' external_id: arxiv: - '1702.01136' intvolume: ' 34' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1702.01136 month: '01' oa: 1 oa_version: Preprint page: 130-162 publication: SIAM Journal on Discrete Mathematics publication_identifier: eissn: - 1095-7146 issn: - 0895-4801 publication_status: published publisher: Society for Industrial & Applied Mathematics quality_controlled: '1' related_material: record: - id: '11831' relation: earlier_version status: public scopus_import: '1' status: public title: Improved guarantees for vertex sparsification in planar graphs type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 34 year: '2020' ... --- _id: '11954' abstract: - lang: eng text: The combination of nickel and photocatalysis has unlocked a variety of cross-couplings. These protocols rely on a few photocatalysts that can only convert a small portion of visible light (<500 nm) into chemical energy. The high-energy photons that excite the photocatalyst can result in unwanted side reactions. Dyes that absorb a much broader spectrum of light are not applicable because of their short-lived singlet excited states. Here, we describe a self-assembling catalyst system that overcomes this limitation. Immobilization of a nickel catalyst on dye-sensitized titanium dioxide results in a material that catalyzes carbon–heteroatom and carbon–carbon bond formations. The modular approach of dye-sensitized metallaphotocatalysts accesses the entire visible light spectrum and allows tackling selectivity issues resulting from low wavelengths strategically. The concept overcomes current limitations of metallaphotocatalysis by unlocking the potential of dyes that were previously unsuitable. article_processing_charge: No article_type: original author: - first_name: Susanne full_name: Reischauer, Susanne last_name: Reischauer - first_name: Volker full_name: Strauss, Volker last_name: Strauss - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X citation: ama: Reischauer S, Strauss V, Pieber B. Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum. ACS Catalysis. 2020;10(22):13269–13274. doi:10.1021/acscatal.0c03950 apa: Reischauer, S., Strauss, V., & Pieber, B. (2020). Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum. ACS Catalysis. American Chemical Society. https://doi.org/10.1021/acscatal.0c03950 chicago: Reischauer, Susanne, Volker Strauss, and Bartholomäus Pieber. “Modular, Self-Assembling Metallaphotocatalyst for Cross-Couplings Using the Full Visible-Light Spectrum.” ACS Catalysis. American Chemical Society, 2020. https://doi.org/10.1021/acscatal.0c03950. ieee: S. Reischauer, V. Strauss, and B. Pieber, “Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum,” ACS Catalysis, vol. 10, no. 22. American Chemical Society, pp. 13269–13274, 2020. ista: Reischauer S, Strauss V, Pieber B. 2020. Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum. ACS Catalysis. 10(22), 13269–13274. mla: Reischauer, Susanne, et al. “Modular, Self-Assembling Metallaphotocatalyst for Cross-Couplings Using the Full Visible-Light Spectrum.” ACS Catalysis, vol. 10, no. 22, American Chemical Society, 2020, pp. 13269–13274, doi:10.1021/acscatal.0c03950. short: S. Reischauer, V. Strauss, B. Pieber, ACS Catalysis 10 (2020) 13269–13274. date_created: 2022-08-24T10:40:46Z date_published: 2020-11-02T00:00:00Z date_updated: 2024-10-14T11:42:40Z day: '02' doi: 10.1021/acscatal.0c03950 extern: '1' intvolume: ' 10' issue: '22' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.26434/chemrxiv.12444908 month: '11' oa: 1 oa_version: Preprint page: 13269–13274 publication: ACS Catalysis publication_identifier: eissn: - 2155-5435 publication_status: published publisher: American Chemical Society quality_controlled: '1' scopus_import: '1' status: public title: Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 10 year: '2020' ... --- _id: '11966' abstract: - lang: eng text: The front cover artwork is provided by the group of Dr. Bartholomäus Pieber at the Max Planck Institute of Colloids and Interfaces (Germany). The image symbolizes the activation of a heterogeneous photocatalyst by visible light and its application for organic synthesis. Read the full text of the Review at 10.1002/cptc.202000014. article_processing_charge: No article_type: original author: - first_name: Sebastian full_name: Gisbertz, Sebastian last_name: Gisbertz - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X citation: ama: Gisbertz S, Pieber B. Heterogeneous photocatalysis in organic synthesis. ChemPhotoChem. 2020;4(7):454-454. doi:10.1002/cptc.202000137 apa: Gisbertz, S., & Pieber, B. (2020). Heterogeneous photocatalysis in organic synthesis. ChemPhotoChem. Wiley. https://doi.org/10.1002/cptc.202000137 chicago: Gisbertz, Sebastian, and Bartholomäus Pieber. “Heterogeneous Photocatalysis in Organic Synthesis.” ChemPhotoChem. Wiley, 2020. https://doi.org/10.1002/cptc.202000137. ieee: S. Gisbertz and B. Pieber, “Heterogeneous photocatalysis in organic synthesis,” ChemPhotoChem, vol. 4, no. 7. Wiley, pp. 454–454, 2020. ista: Gisbertz S, Pieber B. 2020. Heterogeneous photocatalysis in organic synthesis. ChemPhotoChem. 4(7), 454–454. mla: Gisbertz, Sebastian, and Bartholomäus Pieber. “Heterogeneous Photocatalysis in Organic Synthesis.” ChemPhotoChem, vol. 4, no. 7, Wiley, 2020, pp. 454–454, doi:10.1002/cptc.202000137. short: S. Gisbertz, B. Pieber, ChemPhotoChem 4 (2020) 454–454. date_created: 2022-08-25T08:33:38Z date_published: 2020-07-01T00:00:00Z date_updated: 2024-10-14T12:06:48Z day: '01' doi: 10.1002/cptc.202000137 extern: '1' intvolume: ' 4' issue: '7' language: - iso: eng month: '07' oa_version: None page: 454-454 publication: ChemPhotoChem publication_identifier: eissn: - 2367-0932 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Heterogeneous photocatalysis in organic synthesis type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 4 year: '2020' ... --- _id: '11969' abstract: - lang: eng text: Photochemistry enables new synthetic means to form carbon–heteroatom bonds. Photocatalysts can catalyze carbon–heteroatom cross-couplings by electron or energy transfer either alone or in combination with a second catalyst. Photocatalyst-free methods are possible using photolabile substrates or by generating photoactive electron donor-acceptor complexes. This review summarizes and discusses the strategies used in light-mediated carbon–heteroatom bond formations based on the proposed mechanisms. article_processing_charge: No article_type: review author: - first_name: Cristian full_name: Cavedon, Cristian last_name: Cavedon - first_name: Peter H. full_name: Seeberger, Peter H. last_name: Seeberger - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X citation: ama: Cavedon C, Seeberger PH, Pieber B. Photochemical strategies for carbon–heteroatom bond formation. European Journal of Organic Chemistry. 2020;2020(10):1379-1392. doi:10.1002/ejoc.201901173 apa: Cavedon, C., Seeberger, P. H., & Pieber, B. (2020). Photochemical strategies for carbon–heteroatom bond formation. European Journal of Organic Chemistry. Wiley. https://doi.org/10.1002/ejoc.201901173 chicago: Cavedon, Cristian, Peter H. Seeberger, and Bartholomäus Pieber. “Photochemical Strategies for Carbon–Heteroatom Bond Formation.” European Journal of Organic Chemistry. Wiley, 2020. https://doi.org/10.1002/ejoc.201901173. ieee: C. Cavedon, P. H. Seeberger, and B. Pieber, “Photochemical strategies for carbon–heteroatom bond formation,” European Journal of Organic Chemistry, vol. 2020, no. 10. Wiley, pp. 1379–1392, 2020. ista: Cavedon C, Seeberger PH, Pieber B. 2020. Photochemical strategies for carbon–heteroatom bond formation. European Journal of Organic Chemistry. 2020(10), 1379–1392. mla: Cavedon, Cristian, et al. “Photochemical Strategies for Carbon–Heteroatom Bond Formation.” European Journal of Organic Chemistry, vol. 2020, no. 10, Wiley, 2020, pp. 1379–92, doi:10.1002/ejoc.201901173. short: C. Cavedon, P.H. Seeberger, B. Pieber, European Journal of Organic Chemistry 2020 (2020) 1379–1392. date_created: 2022-08-25T08:49:25Z date_published: 2020-03-15T00:00:00Z date_updated: 2024-10-14T12:06:58Z day: '15' doi: 10.1002/ejoc.201901173 extern: '1' intvolume: ' 2020' issue: '10' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1002/ejoc.201901173 month: '03' oa: 1 oa_version: Published Version page: 1379-1392 publication: European Journal of Organic Chemistry publication_identifier: eissn: - 1099-0690 issn: - 1434-193X publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Photochemical strategies for carbon–heteroatom bond formation type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2020 year: '2020' ... --- _id: '11978' abstract: - lang: eng text: Dual photocatalysis and nickel catalysis can effect cross-coupling under mild conditions, but little is known about the in situ kinetics of this class of reactions. We report a comprehensive kinetic examination of a model carboxylate O-arylation, comparing a state-of-the-art homogeneous photocatalyst (Ir(ppy)3) with a competitive heterogeneous photocatalyst (graphitic carbon nitride). Experimental conditions were adjusted such that the nickel catalytic cycle is saturated with excited photocatalyst. This approach was designed to remove the role of the photocatalyst, by which only the intrinsic behaviors of the nickel catalytic cycles are observed. The two reactions did not display identical kinetics. Ir(ppy)3 deactivates the nickel catalytic cycle and creates more dehalogenated side product. Kinetic data for the reaction using Ir(ppy)3 supports a turnover-limiting reductive elimination. Graphitic carbon nitride gave higher selectivity, even at high photocatalyst-to-nickel ratios. The heterogeneous reaction also showed a rate dependence on aryl halide, indicating that oxidative addition plays a role in rate determination. The results argue against the current mechanistic hypothesis, which states that the photocatalyst is only involved to trigger reductive elimination. article_processing_charge: No article_type: original author: - first_name: Jamal A. full_name: Malik, Jamal A. last_name: Malik - first_name: Amiera full_name: Madani, Amiera last_name: Madani - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X - first_name: Peter H. full_name: Seeberger, Peter H. last_name: Seeberger citation: ama: Malik JA, Madani A, Pieber B, Seeberger PH. Evidence for photocatalyst involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations. Journal of the American Chemical Society. 2020;142(25):11042-11049. doi:10.1021/jacs.0c02848 apa: Malik, J. A., Madani, A., Pieber, B., & Seeberger, P. H. (2020). Evidence for photocatalyst involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations. Journal of the American Chemical Society. American Chemical Society. https://doi.org/10.1021/jacs.0c02848 chicago: Malik, Jamal A., Amiera Madani, Bartholomäus Pieber, and Peter H. Seeberger. “Evidence for Photocatalyst Involvement in Oxidative Additions of Nickel-Catalyzed Carboxylate O-Arylations.” Journal of the American Chemical Society. American Chemical Society, 2020. https://doi.org/10.1021/jacs.0c02848. ieee: J. A. Malik, A. Madani, B. Pieber, and P. H. Seeberger, “Evidence for photocatalyst involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations,” Journal of the American Chemical Society, vol. 142, no. 25. American Chemical Society, pp. 11042–11049, 2020. ista: Malik JA, Madani A, Pieber B, Seeberger PH. 2020. Evidence for photocatalyst involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations. Journal of the American Chemical Society. 142(25), 11042–11049. mla: Malik, Jamal A., et al. “Evidence for Photocatalyst Involvement in Oxidative Additions of Nickel-Catalyzed Carboxylate O-Arylations.” Journal of the American Chemical Society, vol. 142, no. 25, American Chemical Society, 2020, pp. 11042–49, doi:10.1021/jacs.0c02848. short: J.A. Malik, A. Madani, B. Pieber, P.H. Seeberger, Journal of the American Chemical Society 142 (2020) 11042–11049. date_created: 2022-08-25T10:57:38Z date_published: 2020-06-24T00:00:00Z date_updated: 2024-10-14T12:06:34Z day: '24' doi: 10.1021/jacs.0c02848 extern: '1' external_id: pmid: - '32469219' intvolume: ' 142' issue: '25' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1021/jacs.0c02848 month: '06' oa: 1 oa_version: Published Version page: 11042-11049 pmid: 1 publication: Journal of the American Chemical Society publication_identifier: eissn: - 1520-5126 issn: - 0002-7863 publication_status: published publisher: American Chemical Society quality_controlled: '1' scopus_import: '1' status: public title: Evidence for photocatalyst involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 142 year: '2020' ... --- _id: '11979' abstract: - lang: eng text: Dual photoredox/nickel-catalysed C–N cross-couplings suffer from low yields for electron-rich aryl halides. The formation of catalytically inactive nickel-black is responsible for this limitation and causes severe reproducibility issues. Here, we demonstrate that catalyst deactivation can be avoided by using a carbon nitride photocatalyst. The broad absorption of the heterogeneous photocatalyst enables wavelength-dependent control of the rate of reductive elimination to prevent nickel-black formation during the coupling of cyclic, secondary amines and aryl halides. A second approach, which is applicable to a broader set of electron-rich aryl halides, is to run the reactions at high concentrations to increase the rate of oxidative addition. Less nucleophilic, primary amines can be coupled with electron-rich aryl halides by stabilizing low-valent nickel intermediates with a suitable additive. The developed protocols enable reproducible, selective C–N cross-couplings of electron-rich aryl bromides and can also be applied for electron-poor aryl chlorides. article_processing_charge: No article_type: original author: - first_name: Sebastian full_name: Gisbertz, Sebastian last_name: Gisbertz - first_name: Susanne full_name: Reischauer, Susanne last_name: Reischauer - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X citation: ama: Gisbertz S, Reischauer S, Pieber B. Overcoming limitations in dual photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation. Nature Catalysis. 2020;3(8):611-620. doi:10.1038/s41929-020-0473-6 apa: Gisbertz, S., Reischauer, S., & Pieber, B. (2020). Overcoming limitations in dual photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation. Nature Catalysis. Springer Nature. https://doi.org/10.1038/s41929-020-0473-6 chicago: Gisbertz, Sebastian, Susanne Reischauer, and Bartholomäus Pieber. “Overcoming Limitations in Dual Photoredox/Nickel-Catalysed C–N Cross-Couplings Due to Catalyst Deactivation.” Nature Catalysis. Springer Nature, 2020. https://doi.org/10.1038/s41929-020-0473-6. ieee: S. Gisbertz, S. Reischauer, and B. Pieber, “Overcoming limitations in dual photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation,” Nature Catalysis, vol. 3, no. 8. Springer Nature, pp. 611–620, 2020. ista: Gisbertz S, Reischauer S, Pieber B. 2020. Overcoming limitations in dual photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation. Nature Catalysis. 3(8), 611–620. mla: Gisbertz, Sebastian, et al. “Overcoming Limitations in Dual Photoredox/Nickel-Catalysed C–N Cross-Couplings Due to Catalyst Deactivation.” Nature Catalysis, vol. 3, no. 8, Springer Nature, 2020, pp. 611–20, doi:10.1038/s41929-020-0473-6. short: S. Gisbertz, S. Reischauer, B. Pieber, Nature Catalysis 3 (2020) 611–620. date_created: 2022-08-25T11:06:16Z date_published: 2020-08-01T00:00:00Z date_updated: 2024-10-14T12:06:23Z day: '01' doi: 10.1038/s41929-020-0473-6 extern: '1' intvolume: ' 3' issue: '8' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.26434/chemrxiv.10298735 month: '08' oa: 1 oa_version: Preprint page: 611-620 publication: Nature Catalysis publication_identifier: eissn: - 2520-1158 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Overcoming limitations in dual photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 3 year: '2020' ...