---
_id: '11534'
abstract:
- lang: eng
text: The observed properties of the Lyman-α (Ly α) emission line are a powerful
probe of neutral gas in and around galaxies. We present spatially resolved Ly α
spectroscopy with VLT/MUSE targeting VR7, a UV-luminous galaxy at z = 6.532 with
moderate Ly α equivalent width (EW0 ≈ 38 Å). These data are combined with deep
resolved [CII]158μm spectroscopy obtained with ALMA and UV imaging from HST and
we also detect UV continuum with MUSE. Ly α emission is clearly detected with
S/N ≈ 40 and FWHM of 374 km s−1. Ly α and [C II] are similarly extended beyond
the UV, with effective radius reff = 2.1 ± 0.2 kpc for a single exponential model
or reff,Lyα,halo=3.45+1.08−0.87 kpc when measured jointly with the UV continuum.
The Ly α profile is broader and redshifted with respect to the [C II] line (by
213 km s−1), but there are spatial variations that are qualitatively similar in
both lines and coincide with resolved UV components. This suggests that the emission
originates from two components with plausibly different H I column densities.
We place VR7 in the context of other galaxies at similar and lower redshift. The
Ly α halo scale length is similar at different redshifts and velocity shifts with
respect to the systemic are typically smaller. Overall, we find little indications
of a more neutral vicinity at higher redshift. This means that the local (∼10 kpc)
neutral gas conditions that determine the observed Ly α properties in VR7 resemble
the conditions in post-reionization galaxies.
acknowledgement: 'We thank the referee for their suggestions and constructive comments
that helped to improve the presentation of our results. Based on observations obtained
with the Very Large Telescope, program 99.A-0462. Based on observations made with
the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute,
which is operated by the Association of Universities for Research in Astronomy,
Inc., under NASA contract NAS 5-26555. These observations are associated with program
#14699. This paper makes use of the following ALMA data: ADS/JAO.ALMA#2017.1.01451.S.
ALMA is a partnership of ESO (representing its member states), NSF (USA), and NINS
(Japan), together with NRC (Canada) and NSC and ASIAA (Taiwan) and KASI (Republic
of Korea), in cooperation with the Republic of Chile. The Joint ALMA Observatory
is operated by ESO, AUI/NRAO, and NAOJ. MG acknowledges support from NASA grant
NNX17AK58G. GP and SC gratefully acknowledge support from Swiss National Science
Foundation grant PP00P2 163824. BD acknowledges financial support from the National
Science Foundation, grant number 1716907. We have benefited greatly from the public
available programming language PYTHON, including the NUMPY, MATPLOTLIB, SCIPY (Jones
et al. 2001; Hunter 2007; van der Walt, Colbert & Varoquaux 2011) and ASTROPY (Astropy
Collaboration 2013) packages, the astronomical imaging tools SEXTRACTOR, SWARP,
and SCAMP (Bertin & Arnouts 1996; Bertin 2006, 2010) and the TOPCAT analysis tool
(Taylor 2013).'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jorryt J
full_name: Matthee, Jorryt J
id: 7439a258-f3c0-11ec-9501-9df22fe06720
last_name: Matthee
orcid: 0000-0003-2871-127X
- first_name: David
full_name: Sobral, David
last_name: Sobral
- first_name: Max
full_name: Gronke, Max
last_name: Gronke
- first_name: Gabriele
full_name: Pezzulli, Gabriele
last_name: Pezzulli
- first_name: Sebastiano
full_name: Cantalupo, Sebastiano
last_name: Cantalupo
- first_name: Huub
full_name: Röttgering, Huub
last_name: Röttgering
- first_name: Behnam
full_name: Darvish, Behnam
last_name: Darvish
- first_name: Sérgio
full_name: Santos, Sérgio
last_name: Santos
citation:
ama: Matthee JJ, Sobral D, Gronke M, et al. Resolved Lyman-α properties of a luminous
Lyman-break galaxy in a large ionized bubble at z = 6.53 . Monthly Notices
of the Royal Astronomical Society. 2020;492(2):1778-1790. doi:10.1093/mnras/stz3554
apa: Matthee, J. J., Sobral, D., Gronke, M., Pezzulli, G., Cantalupo, S., Röttgering,
H., … Santos, S. (2020). Resolved Lyman-α properties of a luminous Lyman-break
galaxy in a large ionized bubble at z = 6.53 . Monthly Notices of the Royal
Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stz3554
chicago: Matthee, Jorryt J, David Sobral, Max Gronke, Gabriele Pezzulli, Sebastiano
Cantalupo, Huub Röttgering, Behnam Darvish, and Sérgio Santos. “Resolved Lyman-α
Properties of a Luminous Lyman-Break Galaxy in a Large Ionized Bubble at z = 6.53
.” Monthly Notices of the Royal Astronomical Society. Oxford University
Press, 2020. https://doi.org/10.1093/mnras/stz3554.
ieee: J. J. Matthee et al., “Resolved Lyman-α properties of a luminous Lyman-break
galaxy in a large ionized bubble at z = 6.53 ,” Monthly Notices of the Royal
Astronomical Society, vol. 492, no. 2. Oxford University Press, pp. 1778–1790,
2020.
ista: Matthee JJ, Sobral D, Gronke M, Pezzulli G, Cantalupo S, Röttgering H, Darvish
B, Santos S. 2020. Resolved Lyman-α properties of a luminous Lyman-break galaxy
in a large ionized bubble at z = 6.53 . Monthly Notices of the Royal Astronomical
Society. 492(2), 1778–1790.
mla: Matthee, Jorryt J., et al. “Resolved Lyman-α Properties of a Luminous Lyman-Break
Galaxy in a Large Ionized Bubble at z = 6.53 .” Monthly Notices of the Royal
Astronomical Society, vol. 492, no. 2, Oxford University Press, 2020, pp.
1778–90, doi:10.1093/mnras/stz3554.
short: J.J. Matthee, D. Sobral, M. Gronke, G. Pezzulli, S. Cantalupo, H. Röttgering,
B. Darvish, S. Santos, Monthly Notices of the Royal Astronomical Society 492 (2020)
1778–1790.
date_created: 2022-07-07T12:21:36Z
date_published: 2020-02-01T00:00:00Z
date_updated: 2022-08-18T11:29:53Z
day: '01'
doi: 10.1093/mnras/stz3554
extern: '1'
external_id:
arxiv:
- '1909.06376'
intvolume: ' 492'
issue: '2'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
- 'galaxies: evolution'
- 'galaxies: high-redshift'
- dark ages
- reionization
- first stars
- 'cosmology: observations'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.06376
month: '02'
oa: 1
oa_version: Preprint
page: 1778-1790
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
eissn:
- 1365-2966
issn:
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Resolved Lyman-α properties of a luminous Lyman-break galaxy in a large ionized
bubble at z = 6.53 '
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 492
year: '2020'
...
---
_id: '11539'
abstract:
- lang: eng
text: 'Despite recent progress in understanding Ly α emitters (LAEs), relatively
little is known regarding their typical black hole activity across cosmic time.
Here, we study the X-ray and radio properties of ∼4000 LAEs at 2.2 < z < 6 from
the SC4K survey in the COSMOS field. We detect 254 (6.8per cent±0.4per cent)
LAEs individually in the X-rays (S/N > 3) with an average luminosity of 1044.31±0.01ergs−1
and average black hole accretion rate (BHAR) of 0.72±0.01 M⊙ yr−1, consistent
with moderate to high accreting active galactic neuclei (AGNs). We detect 120
sources in deep radio data (radio AGN fraction of 3.2per cent±0.3per cent). The
global AGN fraction (8.6per cent±0.4per cent) rises with Ly α luminosity and
declines with increasing redshift. For X-ray-detected LAEs, Ly α luminosities
correlate with the BHARs, suggesting that Ly α luminosity becomes a BHAR indicator.
Most LAEs (93.1per cent±0.6per cent) at 2 < z < 6 have no detectable X-ray emission
(BHARs < 0.017 M⊙ yr−1). The median star formation rate (SFR) of star-forming
LAEs from Ly α and radio luminosities is 7.6+6.6−2.8 M⊙ yr−1. The black hole to
galaxy growth ratio (BHAR/SFR) for LAEs is <0.0022, consistent with typical star-forming
galaxies and the local BHAR/SFR relation. We conclude that LAEs at 2 < z < 6 include
two different populations: an AGN population, where Ly α luminosity traces BHAR,
and another with low SFRs which remain undetected in even the deepest X-ray stacks
but is detected in the radio stacks.'
acknowledgement: JM acknowledges the support of a Huygens PhD fellowship from Leiden
University. We thank Camila Correa for help analysing snipshot merger trees. We
thank the anonymous referee for constructive comments. We also thank Jarle Brinchmann,
Rob Crain, Antonios Katsianis, Paola Popesso, and David Sobral for discussions and
suggestions. We also thank the participants of the Lorentz Center workshop ‘A Decade
of the Star-Forming Main Sequence’ held on 2017 September 4–8, for discussions and
ideas. We have benefited from the public available programming language PYTHON,
including the NUMPY, MATPLOTLIB, and SCIPY (Hunter 2007) packages and the TOPCAT
analysis tool (Taylor 2013).
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: João
full_name: Calhau, João
last_name: Calhau
- first_name: David
full_name: Sobral, David
last_name: Sobral
- first_name: Sérgio
full_name: Santos, Sérgio
last_name: Santos
- first_name: Jorryt J
full_name: Matthee, Jorryt J
id: 7439a258-f3c0-11ec-9501-9df22fe06720
last_name: Matthee
orcid: 0000-0003-2871-127X
- first_name: Ana
full_name: Paulino-Afonso, Ana
last_name: Paulino-Afonso
- first_name: Andra
full_name: Stroe, Andra
last_name: Stroe
- first_name: Brooke
full_name: Simmons, Brooke
last_name: Simmons
- first_name: Cassandra
full_name: Barlow-Hall, Cassandra
last_name: Barlow-Hall
- first_name: Benjamin
full_name: Adams, Benjamin
last_name: Adams
citation:
ama: 'Calhau J, Sobral D, Santos S, et al. The X-ray and radio activity of typical
and luminous Ly α emitters from z ∼ 2 to z ∼ 6: Evidence for a diverse, evolving
population. Monthly Notices of the Royal Astronomical Society. 2020;493(3):3341-3362.
doi:10.1093/mnras/staa476'
apa: 'Calhau, J., Sobral, D., Santos, S., Matthee, J. J., Paulino-Afonso, A., Stroe,
A., … Adams, B. (2020). The X-ray and radio activity of typical and luminous Ly α
emitters from z ∼ 2 to z ∼ 6: Evidence for a diverse, evolving population. Monthly
Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/staa476'
chicago: 'Calhau, João, David Sobral, Sérgio Santos, Jorryt J Matthee, Ana Paulino-Afonso,
Andra Stroe, Brooke Simmons, Cassandra Barlow-Hall, and Benjamin Adams. “The X-Ray
and Radio Activity of Typical and Luminous Ly α Emitters from z ∼ 2 to z ∼ 6:
Evidence for a Diverse, Evolving Population.” Monthly Notices of the Royal
Astronomical Society. Oxford University Press, 2020. https://doi.org/10.1093/mnras/staa476.'
ieee: 'J. Calhau et al., “The X-ray and radio activity of typical and luminous
Ly α emitters from z ∼ 2 to z ∼ 6: Evidence for a diverse, evolving population,”
Monthly Notices of the Royal Astronomical Society, vol. 493, no. 3. Oxford
University Press, pp. 3341–3362, 2020.'
ista: 'Calhau J, Sobral D, Santos S, Matthee JJ, Paulino-Afonso A, Stroe A, Simmons
B, Barlow-Hall C, Adams B. 2020. The X-ray and radio activity of typical and luminous
Ly α emitters from z ∼ 2 to z ∼ 6: Evidence for a diverse, evolving population.
Monthly Notices of the Royal Astronomical Society. 493(3), 3341–3362.'
mla: 'Calhau, João, et al. “The X-Ray and Radio Activity of Typical and Luminous
Ly α Emitters from z ∼ 2 to z ∼ 6: Evidence for a Diverse, Evolving Population.”
Monthly Notices of the Royal Astronomical Society, vol. 493, no. 3, Oxford
University Press, 2020, pp. 3341–62, doi:10.1093/mnras/staa476.'
short: J. Calhau, D. Sobral, S. Santos, J.J. Matthee, A. Paulino-Afonso, A. Stroe,
B. Simmons, C. Barlow-Hall, B. Adams, Monthly Notices of the Royal Astronomical
Society 493 (2020) 3341–3362.
date_created: 2022-07-08T07:34:10Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2022-08-18T11:25:31Z
day: '01'
doi: 10.1093/mnras/staa476
extern: '1'
external_id:
arxiv:
- '1909.11672'
intvolume: ' 493'
issue: '3'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
- 'galaxies: active'
- 'galaxies: evolution'
- 'galaxies: high-redshift'
- 'quasars: supermassive black holes'
- 'galaxies: star formation'
- 'cosmology: observations'
- 'X-rays: galaxies'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.11672
month: '04'
oa: 1
oa_version: Preprint
page: 3341-3362
publication: Monthly Notices of the Royal Astronomical Society
publication_identifier:
eissn:
- 1365-2966
issn:
- 0035-8711
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The X-ray and radio activity of typical and luminous Ly α emitters from z
∼ 2 to z ∼ 6: Evidence for a diverse, evolving population'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 493
year: '2020'
...
---
_id: '11586'
abstract:
- lang: eng
text: Distant luminous Lyman-α emitters are excellent targets for detailed observations
of galaxies in the epoch of reionisation. Spatially resolved observations of these
galaxies allow us to simultaneously probe the emission from young stars, partially
ionised gas in the interstellar medium and to constrain the properties of the
surrounding hydrogen in the circumgalactic medium. We review recent results from
(spectroscopic) follow-up studies of the rest-frame UV, Lyman-α and [CII] emission
in luminous galaxies observed ∼500 Myr after the Big Bang with ALMA, HST/WFC3
and VLT/X-SHOOTER. These galaxies likely reside in early ionised bubbles and are
complex systems, consisting of multiple well separated and resolved components
where traces of metals are already present.
article_processing_charge: No
arxiv: 1
author:
- first_name: Jorryt J
full_name: Matthee, Jorryt J
id: 7439a258-f3c0-11ec-9501-9df22fe06720
last_name: Matthee
orcid: 0000-0003-2871-127X
- first_name: David
full_name: Sobral, David
last_name: Sobral
citation:
ama: 'Matthee JJ, Sobral D. Unveiling the most luminous Lyman-α emitters in the
epoch of reionisation. In: Proceedings of the International Astronomical Union.
Vol 15. Cambridge University Press; 2020:21-25. doi:10.1017/s1743921319009451'
apa: Matthee, J. J., & Sobral, D. (2020). Unveiling the most luminous Lyman-α
emitters in the epoch of reionisation. In Proceedings of the International
Astronomical Union (Vol. 15, pp. 21–25). Cambridge University Press. https://doi.org/10.1017/s1743921319009451
chicago: Matthee, Jorryt J, and David Sobral. “Unveiling the Most Luminous Lyman-α
Emitters in the Epoch of Reionisation.” In Proceedings of the International
Astronomical Union, 15:21–25. Cambridge University Press, 2020. https://doi.org/10.1017/s1743921319009451.
ieee: J. J. Matthee and D. Sobral, “Unveiling the most luminous Lyman-α emitters
in the epoch of reionisation,” in Proceedings of the International Astronomical
Union, 2020, vol. 15, no. S352, pp. 21–25.
ista: Matthee JJ, Sobral D. 2020. Unveiling the most luminous Lyman-α emitters in
the epoch of reionisation. Proceedings of the International Astronomical Union.
vol. 15, 21–25.
mla: Matthee, Jorryt J., and David Sobral. “Unveiling the Most Luminous Lyman-α
Emitters in the Epoch of Reionisation.” Proceedings of the International Astronomical
Union, vol. 15, no. S352, Cambridge University Press, 2020, pp. 21–25, doi:10.1017/s1743921319009451.
short: J.J. Matthee, D. Sobral, in:, Proceedings of the International Astronomical
Union, Cambridge University Press, 2020, pp. 21–25.
date_created: 2022-07-14T14:08:41Z
date_published: 2020-06-04T00:00:00Z
date_updated: 2022-08-19T08:41:12Z
day: '04'
doi: 10.1017/s1743921319009451
extern: '1'
external_id:
arxiv:
- '1911.04774'
intvolume: ' 15'
issue: S352
keyword:
- Astronomy and Astrophysics
- Space and Planetary Science
- 'galaxies: formation'
- 'galaxies: evolution'
- 'galaxies: high-redshift'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1911.04774
month: '06'
oa: 1
oa_version: Preprint
page: 21-25
publication: Proceedings of the International Astronomical Union
publication_identifier:
eissn:
- 1743-9221
issn:
- 1743-9213
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unveiling the most luminous Lyman-α emitters in the epoch of reionisation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2020'
...
---
_id: '11610'
abstract:
- lang: eng
text: Studies of Galactic structure and evolution have benefited enormously from
Gaia kinematic information, though additional, intrinsic stellar parameters like
age are required to best constrain Galactic models. Asteroseismology is the most
precise method of providing such information for field star populations en masse,
but existing samples for the most part have been limited to a few narrow fields
of view by the CoRoT and Kepler missions. In an effort to provide well-characterized
stellar parameters across a wide range in Galactic position, we present the second
data release of red giant asteroseismic parameters for the K2 Galactic Archaeology
Program (GAP). We provide ${\nu }_{\max }$ and ${\rm{\Delta }}\nu $ based on six
independent pipeline analyses; first-ascent red giant branch (RGB) and red clump
(RC) evolutionary state classifications from machine learning; and ready-to-use
radius and mass coefficients, κR and κM, which, when appropriately multiplied
by a solar-scaled effective temperature factor, yield physical stellar radii and
masses. In total, we report 4395 radius and mass coefficients, with typical uncertainties
of 3.3% (stat.) ± 1% (syst.) for κR and 7.7% (stat.) ± 2% (syst.) for κM among
RGB stars, and 5.0% (stat.) ± 1% (syst.) for κR and 10.5% (stat.) ± 2% (syst.)
for κM among RC stars. We verify that the sample is nearly complete—except for
a dearth of stars with ${\nu }_{\max }\lesssim 10\mbox{--}20\,\mu \mathrm{Hz}$—by
comparing to Galactic models and visual inspection. Our asteroseismic radii agree
with radii derived from Gaia Data Release 2 parallaxes to within 2.2% ± 0.3% for
RGB stars and 2.0% ± 0.6% for RC stars.
acknowledgement: "We thank the referee for comments that strengthened the manuscript.
J. C. Z. and M. H. P. acknowledge support from NASA grants 80NSSC18K0391 and NNX17AJ40G.
Y. E. and C. J. acknowledge the support of the UK Science and Technology Facilities
Council (STFC). S. M. would like to acknowledge support from the Spanish Ministry
with the Ramon y Cajal fellowship number RYC-2015-17697. R. A. G. acknowledges funding
received from the PLATO CNES grant. R. S. acknowledges funding via a Royal Society
University Research Fellowship. D.H. acknowledges support from the Alfred P. Sloan
Foundation and the National Aeronautics and Space Administration (80NSSC19K0108).
V.S.A. acknowledges support from the Independent Research Fund Denmark (Research
grant 7027-00096B), and the Carlsberg foundation (grant agreement CF19-0649). This
research was supported in part by the National Science Foundation under grant No.
NSF PHY-1748958.\r\n\r\nFunding for the Stellar Astrophysics Centre (SAC) is provided
by The Danish National Research Foundation (grant agreement No. DNRF106).\r\n\r\nThe
K2 Galactic Archaeology Program is supported by the National Aeronautics and Space
Administration under grant NNX16AJ17G issued through the K2 Guest Observer Program.\r\n\r\nThis
publication makes use of data products from the Two Micron All Sky Survey, which
is a joint project of the University of Massachusetts and the Infrared Processing
and Analysis Center/California Institute of Technology, funded by the National Aeronautics
and Space Administration and the National Science Foundation.\r\n\r\nThis work has
made use of data from the European Space Agency (ESA) mission Gaia (https://www.cosmos.esa.int/gaia),
processed by the Gaia Data Processing and Analysis Consortium (DPAC, https://www.cosmos.esa.int/web/gaia/dpac/consortium).
Funding for the DPAC has been provided by national institutions, in particular the
institutions participating in the Gaia Multilateral Agreement.\r\n\r\nFunding for
the Sloan Digital Sky Survey IV has been provided by the Alfred P. Sloan Foundation,
the U.S. Department of Energy Office of Science, and the Participating Institutions.
SDSS-IV acknowledges support and resources from the Center for High Performance
Computing at the University of Utah. The SDSS website is www.sdss.org.\r\n\r\nSDSS-IV
is managed by the Astrophysical Research Consortium for the Participating Institutions
of the SDSS Collaboration, including the Brazilian Participation Group, the Carnegie
Institution for Science, Carnegie Mellon University, the Chilean Participation Group,
the French Participation Group, the Harvard–Smithsonian Center for Astrophysics,
Instituto de Astrofísica de Canarias, The Johns Hopkins University, Kavli Institute
for the Physics and Mathematics of the Universe (IPMU)/University of Tokyo, the
Korean Participation Group, Lawrence Berkeley National Laboratory, Leibniz Institut
für Astrophysik Potsdam (AIP), Max-Planck-Institut für Astronomie (MPIA Heidelberg),
Max-Planck-Institut für Astrophysik (MPA Garching), Max-Planck-Institut für Extraterrestrische
Physik (MPE), National Astronomical Observatories of China, New Mexico State University,
New York University, University of Notre Dame, Observatário Nacional/MCTI, The Ohio
State University, Pennsylvania State University, Shanghai Astronomical Observatory,
United Kingdom Participation Group, Universidad Nacional Autónoma de México, University
of Arizona, University of Colorado Boulder, University of Oxford, University of
Portsmouth, University of Utah, University of Virginia, University of Washington,
University of Wisconsin, Vanderbilt University, and Yale University.\r\n\r\nSoftware:
asfgrid (Sharma & Stello 2016), emcee (Foreman-Mackey et al. 2013), NumPy (Walt
2011), pandas (McKinney 2010; Reback et al. 2020), Matplotlib (Hunter 2007), IPython
(Pérez & Granger 2007), SciPy (Virtanen et al. 2020)."
article_number: '23'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Joel C.
full_name: Zinn, Joel C.
last_name: Zinn
- first_name: Dennis
full_name: Stello, Dennis
last_name: Stello
- 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: Thomas
full_name: Kallinger, Thomas
last_name: Kallinger
- first_name: Savita
full_name: Mathur, Savita
last_name: Mathur
- first_name: Benoît
full_name: Mosser, Benoît
last_name: Mosser
- 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: Caitlin
full_name: Jones, Caitlin
last_name: Jones
- first_name: Marc
full_name: Hon, Marc
last_name: Hon
- first_name: Sanjib
full_name: Sharma, Sanjib
last_name: Sharma
- first_name: Ralph
full_name: Schönrich, Ralph
last_name: Schönrich
- first_name: Jack T.
full_name: Warfield, Jack T.
last_name: Warfield
- first_name: Rodrigo
full_name: Luger, Rodrigo
last_name: Luger
- first_name: Marc H.
full_name: Pinsonneault, Marc H.
last_name: Pinsonneault
- first_name: Jennifer A.
full_name: Johnson, Jennifer A.
last_name: Johnson
- first_name: Daniel
full_name: Huber, Daniel
last_name: Huber
- first_name: Victor Silva
full_name: Aguirre, Victor Silva
last_name: Aguirre
- first_name: William J.
full_name: Chaplin, William J.
last_name: Chaplin
- first_name: Guy R.
full_name: Davies, Guy R.
last_name: Davies
- first_name: Andrea
full_name: Miglio, Andrea
last_name: Miglio
citation:
ama: 'Zinn JC, Stello D, Elsworth Y, et al. The K2 galactic archaeology program
data release 2: Asteroseismic results from campaigns 4, 6, and 7. The Astrophysical
Journal Supplement Series. 2020;251(2). doi:10.3847/1538-4365/abbee3'
apa: 'Zinn, J. C., Stello, D., Elsworth, Y., García, R. A., Kallinger, T., Mathur,
S., … Miglio, A. (2020). The K2 galactic archaeology program data release 2: Asteroseismic
results from campaigns 4, 6, and 7. The Astrophysical Journal Supplement Series.
IOP Publishing. https://doi.org/10.3847/1538-4365/abbee3'
chicago: 'Zinn, Joel C., Dennis Stello, Yvonne Elsworth, Rafael A. García, Thomas
Kallinger, Savita Mathur, Benoît Mosser, et al. “The K2 Galactic Archaeology Program
Data Release 2: Asteroseismic Results from Campaigns 4, 6, and 7.” The Astrophysical
Journal Supplement Series. IOP Publishing, 2020. https://doi.org/10.3847/1538-4365/abbee3.'
ieee: 'J. C. Zinn et al., “The K2 galactic archaeology program data release
2: Asteroseismic results from campaigns 4, 6, and 7,” The Astrophysical Journal
Supplement Series, vol. 251, no. 2. IOP Publishing, 2020.'
ista: 'Zinn JC, Stello D, Elsworth Y, García RA, Kallinger T, Mathur S, Mosser B,
Bugnet LA, Jones C, Hon M, Sharma S, Schönrich R, Warfield JT, Luger R, Pinsonneault
MH, Johnson JA, Huber D, Aguirre VS, Chaplin WJ, Davies GR, Miglio A. 2020. The
K2 galactic archaeology program data release 2: Asteroseismic results from campaigns
4, 6, and 7. The Astrophysical Journal Supplement Series. 251(2), 23.'
mla: 'Zinn, Joel C., et al. “The K2 Galactic Archaeology Program Data Release 2:
Asteroseismic Results from Campaigns 4, 6, and 7.” The Astrophysical Journal
Supplement Series, vol. 251, no. 2, 23, IOP Publishing, 2020, doi:10.3847/1538-4365/abbee3.'
short: J.C. Zinn, D. Stello, Y. Elsworth, R.A. García, T. Kallinger, S. Mathur,
B. Mosser, L.A. Bugnet, C. Jones, M. Hon, S. Sharma, R. Schönrich, J.T. Warfield,
R. Luger, M.H. Pinsonneault, J.A. Johnson, D. Huber, V.S. Aguirre, W.J. Chaplin,
G.R. Davies, A. Miglio, The Astrophysical Journal Supplement Series 251 (2020).
date_created: 2022-07-18T13:27:26Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2022-08-22T07:04:45Z
day: '01'
doi: 10.3847/1538-4365/abbee3
extern: '1'
external_id:
arxiv:
- '2012.04051'
intvolume: ' 251'
issue: '2'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.04051
month: '12'
oa: 1
oa_version: Preprint
publication: The Astrophysical Journal Supplement Series
publication_identifier:
eissn:
- 1538-4365
issn:
- 0067-0049
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The K2 galactic archaeology program data release 2: Asteroseismic results
from campaigns 4, 6, and 7'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 251
year: '2020'
...
---
_id: '11611'
abstract:
- lang: eng
text: Over the course of its history, the Milky Way has ingested multiple smaller
satellite galaxies1. Although these accreted stellar populations can be forensically
identified as kinematically distinct structures within the Galaxy, it is difficult
in general to date precisely the age at which any one merger occurred. Recent
results have revealed a population of stars that were accreted via the collision
of a dwarf galaxy, called Gaia–Enceladus1, leading to substantial pollution of
the chemical and dynamical properties of the Milky Way. Here we identify the very
bright, naked-eye star ν Indi as an indicator of the age of the early in situ
population of the Galaxy. We combine asteroseismic, spectroscopic, astrometric
and kinematic observations to show that this metal-poor, alpha-element-rich star
was an indigenous member of the halo, and we measure its age to be 11.0±0.7 (stat)
±0.8 (sys) billion years. The star bears hallmarks consistent with having been
kinematically heated by the Gaia–Enceladus collision. Its age implies that the
earliest the merger could have begun was 11.6 and 13.2 billion years ago, at 68%
and 95% confidence, respectively. Computations based on hierarchical cosmological
models slightly reduce the above limits.
acknowledgement: This paper includes data collected by the TESS mission, which are
publicly available from the Mikulski Archive for Space Telescopes (MAST). 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. W.J.C. acknowledges support from the
UK Science and Technology Facilities Council (STFC) and UK Space Agency. Funding
for the Stellar Astrophysics Centre is provided by The Danish National Research
Foundation (grant agreement number DNRF106). This research was partially conducted
during the Exostar19 programme at the Kavli Institute for Theoretical Physics at
UC Santa Barbara, which was supported in part by the National Science Foundation
under grant number NSF PHY-1748958. A.M., J.T.M., F.V. and J.M. acknowledge support
from the ERC Consolidator Grant funding scheme (project ASTEROCHRONOMETRY, grant
agreement number 772293). F.V. acknowledges the support of a Fellowship from the
Center for Cosmology and AstroParticle Physics at The Ohio State University. W.H.B.
and M.B.N. acknowledge support from the UK Space Agency. K.J.B. is supported by
the National Science Foundation under award AST-1903828. M.B.N. acknowledges partial
support from the NYU Abu Dhabi Center for Space Science under grant number G1502.
A.M.S. is partially supported by the Spanish Government (ESP2017-82674-R) and Generalitat
de Catalunya (2017-SGR-1131). T.M. acknowledges financial support from Belspo for
contract PRODEX PLATO. H.K. acknowledges support from the European Social Fund via
the Lithuanian Science Council grant number 09.3.3-LMT-K-712-01-0103. S.B. acknowledges
support from NSF grant AST-1514676 and NASA grant 80NSSC19K0374. V.S.A. acknowledges
support from the Independent Research Fund Denmark (research grant 7027-00096B).
D.H. acknowledges support by the National Aeronautics and Space Administration (80NSSC18K1585,
80NSSC19K0379) awarded through the TESS Guest Investigator Program and by the National
Science Foundation (AST-1717000). T.S.M. acknowledges support from a visiting fellowship
at the Max Planck Institute for Solar System Research. Computational resources were
provided through XSEDE allocation TG-AST090107. D.L.B. acknowledges support from
NASA under 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 number 792848 (PULSATION). This work was supported by FCT/MCTES
through national funds (PIDDAC) by means of grant UID/FIS/04434/2019. K.J.B., S.H.,
J.S.K. and N.T. are supported by the European Research Council under the European
Community’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement number
338251 (StellarAges). E.C. is funded by the European Union’s Horizon 2020 research
and innovation program under the Marie Sklodowska-Curie grant agreement number 664931.
L.G.-C. acknowledges support from the MINECO FPI-SO doctoral research project SEV-2015-0548-17-2
and predoctoral contract BES-2017-082610. P.G. is supported by the German space
agency (Deutsches Zentrum für Luft- und Raumfahrt) under PLATO data grant 50OO1501.
R.K. acknowledges support from the UK Science and Technology Facilities Council
(STFC), under consolidated grant ST/L000733/1. M.S.L. is supported by the Carlsberg
Foundation (grant agreement number CF17-076). Z.C.O., S.O. and M.Y. acknowledge
support from the Scientific and Technological Research Council of Turkey (TÜBİTAK:118F352).
S.M. acknowledges support from the Spanish ministry through the Ramon y Cajal fellowship
number RYC-2015-17697. T.S.R. acknowledges financial support from Premiale 2015
MITiC (PI B. Garilli). R.Sz. acknowledges the support from NKFIH grant project No.
K-115709, and the Lendület program of the Hungarian Academy of Science (project
number 2018-7/2019). J.T. acknowledges support was provided by NASA through the
NASA Hubble Fellowship grant number 51424 awarded by the Space Telescope Science
Institute, which is operated by the Association of Universities for Research in
Astronomy, Inc., for NASA, under contract NAS5-26555. This work was supported by
FEDER through COMPETE2020 (POCI-01-0145-FEDER-030389. A.M.B. acknowledges funding
from the European Union’s Horizon 2020 research and innovation program under the
Marie Sklodowska-Curie grant agreement No 749962 (project THOT). A.M. and P.R. acknowledge
the support of the Government of India, Department of Atomic Energy, under Project
No. 12-R&D-TFR-6.04-0600. K.J.B. is an NSF Astronomy and Astrophysics Postdoctoral
Fellow and DIRAC Fellow.
article_processing_charge: No
article_type: letter_note
arxiv: 1
author:
- first_name: William J.
full_name: Chaplin, William J.
last_name: Chaplin
- first_name: Aldo M.
full_name: Serenelli, Aldo M.
last_name: Serenelli
- first_name: Andrea
full_name: Miglio, Andrea
last_name: Miglio
- first_name: Thierry
full_name: Morel, Thierry
last_name: Morel
- first_name: J. Ted
full_name: Mackereth, J. Ted
last_name: Mackereth
- first_name: Fiorenzo
full_name: Vincenzo, Fiorenzo
last_name: Vincenzo
- first_name: Hans
full_name: Kjeldsen, Hans
last_name: Kjeldsen
- first_name: Sarbani
full_name: Basu, Sarbani
last_name: Basu
- first_name: Warrick H.
full_name: Ball, Warrick H.
last_name: Ball
- first_name: Amalie
full_name: Stokholm, Amalie
last_name: Stokholm
- first_name: Kuldeep
full_name: Verma, Kuldeep
last_name: Verma
- first_name: Jakob Rørsted
full_name: Mosumgaard, Jakob Rørsted
last_name: Mosumgaard
- first_name: Victor
full_name: Silva Aguirre, Victor
last_name: Silva Aguirre
- first_name: Anwesh
full_name: Mazumdar, Anwesh
last_name: Mazumdar
- first_name: Pritesh
full_name: Ranadive, Pritesh
last_name: Ranadive
- first_name: H. M.
full_name: Antia, H. M.
last_name: Antia
- first_name: Yveline
full_name: Lebreton, Yveline
last_name: Lebreton
- first_name: Joel
full_name: Ong, Joel
last_name: Ong
- first_name: Thierry
full_name: Appourchaux, Thierry
last_name: Appourchaux
- first_name: Timothy R.
full_name: Bedding, Timothy R.
last_name: Bedding
- first_name: Jørgen
full_name: Christensen-Dalsgaard, Jørgen
last_name: Christensen-Dalsgaard
- first_name: Orlagh
full_name: Creevey, Orlagh
last_name: Creevey
- first_name: Rafael A.
full_name: García, Rafael A.
last_name: García
- first_name: Rasmus
full_name: Handberg, Rasmus
last_name: Handberg
- first_name: Daniel
full_name: Huber, Daniel
last_name: Huber
- first_name: Steven D.
full_name: Kawaler, Steven D.
last_name: Kawaler
- first_name: Mikkel N.
full_name: Lund, Mikkel N.
last_name: Lund
- first_name: Travis S.
full_name: Metcalfe, Travis S.
last_name: Metcalfe
- first_name: Keivan G.
full_name: Stassun, Keivan G.
last_name: Stassun
- first_name: Michäel
full_name: Bazot, Michäel
last_name: Bazot
- 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: Maria
full_name: Bergemann, Maria
last_name: Bergemann
- first_name: Derek L.
full_name: Buzasi, Derek L.
last_name: Buzasi
- first_name: Othman
full_name: Benomar, Othman
last_name: Benomar
- 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: Tiago L.
full_name: Campante, Tiago L.
last_name: Campante
- first_name: Zeynep Çelik
full_name: Orhan, Zeynep Çelik
last_name: Orhan
- first_name: Enrico
full_name: Corsaro, Enrico
last_name: Corsaro
- first_name: Lucía
full_name: González-Cuesta, Lucía
last_name: González-Cuesta
- first_name: Guy R.
full_name: Davies, Guy R.
last_name: Davies
- first_name: Maria Pia
full_name: Di Mauro, Maria Pia
last_name: Di Mauro
- first_name: Ricky
full_name: Egeland, Ricky
last_name: Egeland
- first_name: Yvonne P.
full_name: Elsworth, Yvonne P.
last_name: Elsworth
- first_name: Patrick
full_name: Gaulme, Patrick
last_name: Gaulme
- first_name: Hamed
full_name: Ghasemi, Hamed
last_name: Ghasemi
- first_name: Zhao
full_name: Guo, Zhao
last_name: Guo
- first_name: Oliver J.
full_name: Hall, Oliver J.
last_name: Hall
- first_name: Amir
full_name: Hasanzadeh, Amir
last_name: Hasanzadeh
- first_name: Saskia
full_name: Hekker, Saskia
last_name: Hekker
- first_name: Rachel
full_name: Howe, Rachel
last_name: Howe
- first_name: Jon M.
full_name: Jenkins, Jon M.
last_name: Jenkins
- first_name: Antonio
full_name: Jiménez, Antonio
last_name: Jiménez
- first_name: René
full_name: Kiefer, René
last_name: Kiefer
- first_name: James S.
full_name: Kuszlewicz, James S.
last_name: Kuszlewicz
- first_name: Thomas
full_name: Kallinger, Thomas
last_name: Kallinger
- first_name: David W.
full_name: Latham, David W.
last_name: Latham
- first_name: Mia S.
full_name: Lundkvist, Mia S.
last_name: Lundkvist
- first_name: Savita
full_name: Mathur, Savita
last_name: Mathur
- first_name: Josefina
full_name: Montalbán, Josefina
last_name: Montalbán
- first_name: Benoit
full_name: Mosser, Benoit
last_name: Mosser
- first_name: Andres Moya
full_name: Bedón, Andres Moya
last_name: Bedón
- first_name: Martin Bo
full_name: Nielsen, Martin Bo
last_name: Nielsen
- first_name: Sibel
full_name: Örtel, Sibel
last_name: Örtel
- first_name: Ben M.
full_name: Rendle, Ben M.
last_name: Rendle
- first_name: George R.
full_name: Ricker, George R.
last_name: Ricker
- first_name: Thaíse S.
full_name: Rodrigues, Thaíse S.
last_name: Rodrigues
- first_name: Ian W.
full_name: Roxburgh, Ian W.
last_name: Roxburgh
- first_name: Hossein
full_name: Safari, Hossein
last_name: Safari
- first_name: Mathew
full_name: Schofield, Mathew
last_name: Schofield
- first_name: Sara
full_name: Seager, Sara
last_name: Seager
- first_name: Barry
full_name: Smalley, Barry
last_name: Smalley
- first_name: Dennis
full_name: Stello, Dennis
last_name: Stello
- first_name: Róbert
full_name: Szabó, Róbert
last_name: Szabó
- first_name: Jamie
full_name: Tayar, Jamie
last_name: Tayar
- first_name: Nathalie
full_name: Themeßl, Nathalie
last_name: Themeßl
- first_name: Alexandra E. L.
full_name: Thomas, Alexandra E. L.
last_name: Thomas
- first_name: Roland K.
full_name: Vanderspek, Roland K.
last_name: Vanderspek
- first_name: Walter E.
full_name: van Rossem, Walter E.
last_name: van Rossem
- first_name: Mathieu
full_name: Vrard, Mathieu
last_name: Vrard
- first_name: Achim
full_name: Weiss, Achim
last_name: Weiss
- first_name: Timothy R.
full_name: White, Timothy R.
last_name: White
- first_name: Joshua N.
full_name: Winn, Joshua N.
last_name: Winn
- first_name: Mutlu
full_name: Yıldız, Mutlu
last_name: Yıldız
citation:
ama: Chaplin WJ, Serenelli AM, Miglio A, et al. Age dating of an early Milky Way
merger via asteroseismology of the naked-eye star ν Indi. Nature Astronomy.
2020;4(4):382-389. doi:10.1038/s41550-019-0975-9
apa: Chaplin, W. J., Serenelli, A. M., Miglio, A., Morel, T., Mackereth, J. T.,
Vincenzo, F., … Yıldız, M. (2020). Age dating of an early Milky Way merger via
asteroseismology of the naked-eye star ν Indi. Nature Astronomy. Springer
Nature. https://doi.org/10.1038/s41550-019-0975-9
chicago: Chaplin, William J., Aldo M. Serenelli, Andrea Miglio, Thierry Morel, J.
Ted Mackereth, Fiorenzo Vincenzo, Hans Kjeldsen, et al. “Age Dating of an Early
Milky Way Merger via Asteroseismology of the Naked-Eye Star ν Indi.” Nature
Astronomy. Springer Nature, 2020. https://doi.org/10.1038/s41550-019-0975-9.
ieee: W. J. Chaplin et al., “Age dating of an early Milky Way merger via
asteroseismology of the naked-eye star ν Indi,” Nature Astronomy, vol.
4, no. 4. Springer Nature, pp. 382–389, 2020.
ista: Chaplin WJ, Serenelli AM, Miglio A, Morel T, Mackereth JT, Vincenzo F, Kjeldsen
H, Basu S, Ball WH, Stokholm A, Verma K, Mosumgaard JR, Silva Aguirre V, Mazumdar
A, Ranadive P, Antia HM, Lebreton Y, Ong J, Appourchaux T, Bedding TR, Christensen-Dalsgaard
J, Creevey O, García RA, Handberg R, Huber D, Kawaler SD, Lund MN, Metcalfe TS,
Stassun KG, Bazot M, Beck PG, Bell KJ, Bergemann M, Buzasi DL, Benomar O, Bossini
D, Bugnet LA, Campante TL, Orhan ZÇ, Corsaro E, González-Cuesta L, Davies GR,
Di Mauro MP, Egeland R, Elsworth YP, Gaulme P, Ghasemi H, Guo Z, Hall OJ, Hasanzadeh
A, Hekker S, Howe R, Jenkins JM, Jiménez A, Kiefer R, Kuszlewicz JS, Kallinger
T, Latham DW, Lundkvist MS, Mathur S, Montalbán J, Mosser B, Bedón AM, Nielsen
MB, Örtel S, Rendle BM, Ricker GR, Rodrigues TS, Roxburgh IW, Safari H, Schofield
M, Seager S, Smalley B, Stello D, Szabó R, Tayar J, Themeßl N, Thomas AEL, Vanderspek
RK, van Rossem WE, Vrard M, Weiss A, White TR, Winn JN, Yıldız M. 2020. Age dating
of an early Milky Way merger via asteroseismology of the naked-eye star ν Indi.
Nature Astronomy. 4(4), 382–389.
mla: Chaplin, William J., et al. “Age Dating of an Early Milky Way Merger via Asteroseismology
of the Naked-Eye Star ν Indi.” Nature Astronomy, vol. 4, no. 4, Springer
Nature, 2020, pp. 382–89, doi:10.1038/s41550-019-0975-9.
short: W.J. Chaplin, A.M. Serenelli, A. Miglio, T. Morel, J.T. Mackereth, F. Vincenzo,
H. Kjeldsen, S. Basu, W.H. Ball, A. Stokholm, K. Verma, J.R. Mosumgaard, V. Silva
Aguirre, A. Mazumdar, P. Ranadive, H.M. Antia, Y. Lebreton, J. Ong, T. Appourchaux,
T.R. Bedding, J. Christensen-Dalsgaard, O. Creevey, R.A. García, R. Handberg,
D. Huber, S.D. Kawaler, M.N. Lund, T.S. Metcalfe, K.G. Stassun, M. Bazot, P.G.
Beck, K.J. Bell, M. Bergemann, D.L. Buzasi, O. Benomar, D. Bossini, L.A. Bugnet,
T.L. Campante, Z.Ç. Orhan, E. Corsaro, L. González-Cuesta, G.R. Davies, M.P. Di
Mauro, R. Egeland, Y.P. Elsworth, P. Gaulme, H. Ghasemi, Z. Guo, O.J. Hall, A.
Hasanzadeh, S. Hekker, R. Howe, J.M. Jenkins, A. Jiménez, R. Kiefer, J.S. Kuszlewicz,
T. Kallinger, D.W. Latham, M.S. Lundkvist, S. Mathur, J. Montalbán, B. Mosser,
A.M. Bedón, M.B. Nielsen, S. Örtel, B.M. Rendle, G.R. Ricker, T.S. Rodrigues,
I.W. Roxburgh, H. Safari, M. Schofield, S. Seager, B. Smalley, D. Stello, R. Szabó,
J. Tayar, N. Themeßl, A.E.L. Thomas, R.K. Vanderspek, W.E. van Rossem, M. Vrard,
A. Weiss, T.R. White, J.N. Winn, M. Yıldız, Nature Astronomy 4 (2020) 382–389.
date_created: 2022-07-18T13:36:19Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2022-08-22T07:08:29Z
day: '01'
doi: 10.1038/s41550-019-0975-9
extern: '1'
external_id:
arxiv:
- '2001.04653'
intvolume: ' 4'
issue: '4'
keyword:
- Astronomy and Astrophysics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2001.04653
month: '04'
oa: 1
oa_version: Preprint
page: 382-389
publication: Nature Astronomy
publication_identifier:
eissn:
- 2397-3366
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Age dating of an early Milky Way merger via asteroseismology of the naked-eye
star ν Indi
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2020'
...
---
_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: 2022-08-22T08:07:42Z
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 MH, 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. H., 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 H, 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. H. 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 MH, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize
the sum of radii. Algorithmica. 82(11), 3183–3194.
mla: Henzinger, Monika H., 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.H. 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: 2022-09-12T08:50:14Z
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 MH. 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. H. (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 H 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. H. 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 MH. 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.H. Henzinger, Algorithmica 82 (2020) 1057–1080.
date_created: 2022-07-27T14:31:06Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2022-09-12T08:55:46Z
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 MH, 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. H., 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-14T08:57:55Z
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 MH, 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. H., & 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 H, 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. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in 28th Annual European
Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
ista: 'Henzinger MH, 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 H., 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.H. 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: 2023-02-14T09:29:51Z
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 MH, 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. H., 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-14T09:39:18Z
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 MH, 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. H., & 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 H 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. H. 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 MH, 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.H. 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: 2023-02-14T09:58:42Z
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 MH, 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. H., 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-14T10:00:58Z
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 MH, 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. H., & 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-14T10:03:43Z
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 MH, 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. H., 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 H 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. H. 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 MH, 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.H. 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: 2023-02-17T09:47:36Z
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 MH, 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. H., & 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 H 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. H. 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 MH, 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.H. 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: 2023-02-17T14:00:37Z
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 MH, 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. H., 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-17T14:02:04Z
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 MH, 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. H., 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 H, 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. H. 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 MH, Rao S, Wang D. 2020. Local flow partitioning for faster edge
connectivity. SIAM Journal on Computing. 49(1), 1–36.
mla: Henzinger, Monika H., 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.H. 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: 2023-02-21T16:31:25Z
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 MH, 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. H., & 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 H 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. H. 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 MH, 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.H. 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: 2023-02-21T16:29:44Z
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'
...