---
_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: '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'
...
---
_id: '11954'
abstract:
- lang: eng
text: The combination of nickel and photocatalysis has unlocked a variety of cross-couplings.
These protocols rely on a few photocatalysts that can only convert a small portion
of visible light (<500 nm) into chemical energy. The high-energy photons that
excite the photocatalyst can result in unwanted side reactions. Dyes that absorb
a much broader spectrum of light are not applicable because of their short-lived
singlet excited states. Here, we describe a self-assembling catalyst system that
overcomes this limitation. Immobilization of a nickel catalyst on dye-sensitized
titanium dioxide results in a material that catalyzes carbon–heteroatom and carbon–carbon
bond formations. The modular approach of dye-sensitized metallaphotocatalysts
accesses the entire visible light spectrum and allows tackling selectivity issues
resulting from low wavelengths strategically. The concept overcomes current limitations
of metallaphotocatalysis by unlocking the potential of dyes that were previously
unsuitable.
article_processing_charge: No
article_type: original
author:
- first_name: Susanne
full_name: Reischauer, Susanne
last_name: Reischauer
- first_name: Volker
full_name: Strauss, Volker
last_name: Strauss
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
citation:
ama: Reischauer S, Strauss V, Pieber B. Modular, self-assembling metallaphotocatalyst
for cross-couplings using the full visible-light spectrum. ACS Catalysis.
2020;10(22):13269–13274. doi:10.1021/acscatal.0c03950
apa: Reischauer, S., Strauss, V., & Pieber, B. (2020). Modular, self-assembling
metallaphotocatalyst for cross-couplings using the full visible-light spectrum.
ACS Catalysis. American Chemical Society. https://doi.org/10.1021/acscatal.0c03950
chicago: Reischauer, Susanne, Volker Strauss, and Bartholomäus Pieber. “Modular,
Self-Assembling Metallaphotocatalyst for Cross-Couplings Using the Full Visible-Light
Spectrum.” ACS Catalysis. American Chemical Society, 2020. https://doi.org/10.1021/acscatal.0c03950.
ieee: S. Reischauer, V. Strauss, and B. Pieber, “Modular, self-assembling metallaphotocatalyst
for cross-couplings using the full visible-light spectrum,” ACS Catalysis,
vol. 10, no. 22. American Chemical Society, pp. 13269–13274, 2020.
ista: Reischauer S, Strauss V, Pieber B. 2020. Modular, self-assembling metallaphotocatalyst
for cross-couplings using the full visible-light spectrum. ACS Catalysis. 10(22),
13269–13274.
mla: Reischauer, Susanne, et al. “Modular, Self-Assembling Metallaphotocatalyst
for Cross-Couplings Using the Full Visible-Light Spectrum.” ACS Catalysis,
vol. 10, no. 22, American Chemical Society, 2020, pp. 13269–13274, doi:10.1021/acscatal.0c03950.
short: S. Reischauer, V. Strauss, B. Pieber, ACS Catalysis 10 (2020) 13269–13274.
date_created: 2022-08-24T10:40:46Z
date_published: 2020-11-02T00:00:00Z
date_updated: 2023-02-21T10:09:09Z
day: '02'
doi: 10.1021/acscatal.0c03950
extern: '1'
intvolume: ' 10'
issue: '22'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.26434/chemrxiv.12444908
month: '11'
oa: 1
oa_version: Preprint
page: 13269–13274
publication: ACS Catalysis
publication_identifier:
eissn:
- 2155-5435
publication_status: published
publisher: American Chemical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Modular, self-assembling metallaphotocatalyst for cross-couplings using the
full visible-light spectrum
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10
year: '2020'
...
---
_id: '11969'
abstract:
- lang: eng
text: Photochemistry enables new synthetic means to form carbon–heteroatom bonds.
Photocatalysts can catalyze carbon–heteroatom cross-couplings by electron or energy
transfer either alone or in combination with a second catalyst. Photocatalyst-free
methods are possible using photolabile substrates or by generating photoactive
electron donor-acceptor complexes. This review summarizes and discusses the strategies
used in light-mediated carbon–heteroatom bond formations based on the proposed
mechanisms.
article_processing_charge: No
article_type: review
author:
- first_name: Cristian
full_name: Cavedon, Cristian
last_name: Cavedon
- first_name: Peter H.
full_name: Seeberger, Peter H.
last_name: Seeberger
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
citation:
ama: Cavedon C, Seeberger PH, Pieber B. Photochemical strategies for carbon–heteroatom
bond formation. European Journal of Organic Chemistry. 2020;2020(10):1379-1392.
doi:10.1002/ejoc.201901173
apa: Cavedon, C., Seeberger, P. H., & Pieber, B. (2020). Photochemical strategies
for carbon–heteroatom bond formation. European Journal of Organic Chemistry.
Wiley. https://doi.org/10.1002/ejoc.201901173
chicago: Cavedon, Cristian, Peter H. Seeberger, and Bartholomäus Pieber. “Photochemical
Strategies for Carbon–Heteroatom Bond Formation.” European Journal of Organic
Chemistry. Wiley, 2020. https://doi.org/10.1002/ejoc.201901173.
ieee: C. Cavedon, P. H. Seeberger, and B. Pieber, “Photochemical strategies for
carbon–heteroatom bond formation,” European Journal of Organic Chemistry,
vol. 2020, no. 10. Wiley, pp. 1379–1392, 2020.
ista: Cavedon C, Seeberger PH, Pieber B. 2020. Photochemical strategies for carbon–heteroatom
bond formation. European Journal of Organic Chemistry. 2020(10), 1379–1392.
mla: Cavedon, Cristian, et al. “Photochemical Strategies for Carbon–Heteroatom Bond
Formation.” European Journal of Organic Chemistry, vol. 2020, no. 10, Wiley,
2020, pp. 1379–92, doi:10.1002/ejoc.201901173.
short: C. Cavedon, P.H. Seeberger, B. Pieber, European Journal of Organic Chemistry
2020 (2020) 1379–1392.
date_created: 2022-08-25T08:49:25Z
date_published: 2020-03-15T00:00:00Z
date_updated: 2023-02-21T10:09:47Z
day: '15'
doi: 10.1002/ejoc.201901173
extern: '1'
intvolume: ' 2020'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1002/ejoc.201901173
month: '03'
oa: 1
oa_version: Published Version
page: 1379-1392
publication: European Journal of Organic Chemistry
publication_identifier:
eissn:
- 1099-0690
issn:
- 1434-193X
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Photochemical strategies for carbon–heteroatom bond formation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020
year: '2020'
...
---
_id: '11978'
abstract:
- lang: eng
text: Dual photocatalysis and nickel catalysis can effect cross-coupling under mild
conditions, but little is known about the in situ kinetics of this class of reactions.
We report a comprehensive kinetic examination of a model carboxylate O-arylation,
comparing a state-of-the-art homogeneous photocatalyst (Ir(ppy)3) with a competitive
heterogeneous photocatalyst (graphitic carbon nitride). Experimental conditions
were adjusted such that the nickel catalytic cycle is saturated with excited photocatalyst.
This approach was designed to remove the role of the photocatalyst, by which only
the intrinsic behaviors of the nickel catalytic cycles are observed. The two reactions
did not display identical kinetics. Ir(ppy)3 deactivates the nickel catalytic
cycle and creates more dehalogenated side product. Kinetic data for the reaction
using Ir(ppy)3 supports a turnover-limiting reductive elimination. Graphitic carbon
nitride gave higher selectivity, even at high photocatalyst-to-nickel ratios.
The heterogeneous reaction also showed a rate dependence on aryl halide, indicating
that oxidative addition plays a role in rate determination. The results argue
against the current mechanistic hypothesis, which states that the photocatalyst
is only involved to trigger reductive elimination.
article_processing_charge: No
article_type: original
author:
- first_name: Jamal A.
full_name: Malik, Jamal A.
last_name: Malik
- first_name: Amiera
full_name: Madani, Amiera
last_name: Madani
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
- first_name: Peter H.
full_name: Seeberger, Peter H.
last_name: Seeberger
citation:
ama: Malik JA, Madani A, Pieber B, Seeberger PH. Evidence for photocatalyst involvement
in oxidative additions of nickel-catalyzed carboxylate O-arylations. Journal
of the American Chemical Society. 2020;142(25):11042-11049. doi:10.1021/jacs.0c02848
apa: Malik, J. A., Madani, A., Pieber, B., & Seeberger, P. H. (2020). Evidence
for photocatalyst involvement in oxidative additions of nickel-catalyzed carboxylate
O-arylations. Journal of the American Chemical Society. American Chemical
Society. https://doi.org/10.1021/jacs.0c02848
chicago: Malik, Jamal A., Amiera Madani, Bartholomäus Pieber, and Peter H. Seeberger.
“Evidence for Photocatalyst Involvement in Oxidative Additions of Nickel-Catalyzed
Carboxylate O-Arylations.” Journal of the American Chemical Society. American
Chemical Society, 2020. https://doi.org/10.1021/jacs.0c02848.
ieee: J. A. Malik, A. Madani, B. Pieber, and P. H. Seeberger, “Evidence for photocatalyst
involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations,”
Journal of the American Chemical Society, vol. 142, no. 25. American Chemical
Society, pp. 11042–11049, 2020.
ista: Malik JA, Madani A, Pieber B, Seeberger PH. 2020. Evidence for photocatalyst
involvement in oxidative additions of nickel-catalyzed carboxylate O-arylations.
Journal of the American Chemical Society. 142(25), 11042–11049.
mla: Malik, Jamal A., et al. “Evidence for Photocatalyst Involvement in Oxidative
Additions of Nickel-Catalyzed Carboxylate O-Arylations.” Journal of the American
Chemical Society, vol. 142, no. 25, American Chemical Society, 2020, pp. 11042–49,
doi:10.1021/jacs.0c02848.
short: J.A. Malik, A. Madani, B. Pieber, P.H. Seeberger, Journal of the American
Chemical Society 142 (2020) 11042–11049.
date_created: 2022-08-25T10:57:38Z
date_published: 2020-06-24T00:00:00Z
date_updated: 2023-02-21T10:10:06Z
day: '24'
doi: 10.1021/jacs.0c02848
extern: '1'
external_id:
pmid:
- '32469219'
intvolume: ' 142'
issue: '25'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1021/jacs.0c02848
month: '06'
oa: 1
oa_version: Published Version
page: 11042-11049
pmid: 1
publication: Journal of the American Chemical Society
publication_identifier:
eissn:
- 1520-5126
issn:
- 0002-7863
publication_status: published
publisher: American Chemical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Evidence for photocatalyst involvement in oxidative additions of nickel-catalyzed
carboxylate O-arylations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 142
year: '2020'
...
---
_id: '11979'
abstract:
- lang: eng
text: Dual photoredox/nickel-catalysed C–N cross-couplings suffer from low yields
for electron-rich aryl halides. The formation of catalytically inactive nickel-black
is responsible for this limitation and causes severe reproducibility issues. Here,
we demonstrate that catalyst deactivation can be avoided by using a carbon nitride
photocatalyst. The broad absorption of the heterogeneous photocatalyst enables
wavelength-dependent control of the rate of reductive elimination to prevent nickel-black
formation during the coupling of cyclic, secondary amines and aryl halides. A
second approach, which is applicable to a broader set of electron-rich aryl halides,
is to run the reactions at high concentrations to increase the rate of oxidative
addition. Less nucleophilic, primary amines can be coupled with electron-rich
aryl halides by stabilizing low-valent nickel intermediates with a suitable additive.
The developed protocols enable reproducible, selective C–N cross-couplings of
electron-rich aryl bromides and can also be applied for electron-poor aryl chlorides.
article_processing_charge: No
article_type: original
author:
- first_name: Sebastian
full_name: Gisbertz, Sebastian
last_name: Gisbertz
- first_name: Susanne
full_name: Reischauer, Susanne
last_name: Reischauer
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
citation:
ama: Gisbertz S, Reischauer S, Pieber B. Overcoming limitations in dual photoredox/nickel-catalysed
C–N cross-couplings due to catalyst deactivation. Nature Catalysis. 2020;3(8):611-620.
doi:10.1038/s41929-020-0473-6
apa: Gisbertz, S., Reischauer, S., & Pieber, B. (2020). Overcoming limitations
in dual photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation.
Nature Catalysis. Springer Nature. https://doi.org/10.1038/s41929-020-0473-6
chicago: Gisbertz, Sebastian, Susanne Reischauer, and Bartholomäus Pieber. “Overcoming
Limitations in Dual Photoredox/Nickel-Catalysed C–N Cross-Couplings Due to Catalyst
Deactivation.” Nature Catalysis. Springer Nature, 2020. https://doi.org/10.1038/s41929-020-0473-6.
ieee: S. Gisbertz, S. Reischauer, and B. Pieber, “Overcoming limitations in dual
photoredox/nickel-catalysed C–N cross-couplings due to catalyst deactivation,”
Nature Catalysis, vol. 3, no. 8. Springer Nature, pp. 611–620, 2020.
ista: Gisbertz S, Reischauer S, Pieber B. 2020. Overcoming limitations in dual photoredox/nickel-catalysed
C–N cross-couplings due to catalyst deactivation. Nature Catalysis. 3(8), 611–620.
mla: Gisbertz, Sebastian, et al. “Overcoming Limitations in Dual Photoredox/Nickel-Catalysed
C–N Cross-Couplings Due to Catalyst Deactivation.” Nature Catalysis, vol.
3, no. 8, Springer Nature, 2020, pp. 611–20, doi:10.1038/s41929-020-0473-6.
short: S. Gisbertz, S. Reischauer, B. Pieber, Nature Catalysis 3 (2020) 611–620.
date_created: 2022-08-25T11:06:16Z
date_published: 2020-08-01T00:00:00Z
date_updated: 2023-02-21T10:10:09Z
day: '01'
doi: 10.1038/s41929-020-0473-6
extern: '1'
intvolume: ' 3'
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.26434/chemrxiv.10298735
month: '08'
oa: 1
oa_version: Preprint
page: 611-620
publication: Nature Catalysis
publication_identifier:
eissn:
- 2520-1158
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Overcoming limitations in dual photoredox/nickel-catalysed C–N cross-couplings
due to catalyst deactivation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2020'
...
---
_id: '11980'
abstract:
- lang: eng
text: Small organic radicals are ubiquitous intermediates in photocatalysis and
are used in organic synthesis to install functional groups and to tune electronic
properties and pharmacokinetic parameters of the final molecule. Development of
new methods to generate small organic radicals with added functionality can further
extend the utility of photocatalysis for synthetic needs. Herein, we present a
method to generate dichloromethyl radicals from chloroform using a heterogeneous
potassium poly(heptazine imide) (K-PHI) photocatalyst under visible light irradiation
for C1-extension of the enone backbone. The method is applied on 15 enones, with
γ,γ-dichloroketones yields of 18–89%. Due to negative zeta-potential (−40 mV)
and small particle size (100 nm) K-PHI suspension is used in quasi-homogeneous
flow-photoreactor increasing the productivity by 19 times compared to the batch
approach. The resulting γ,γ-dichloroketones, are used as bifunctional building
blocks to access value-added organic compounds such as substituted furans and
pyrroles.
article_number: '1387'
article_processing_charge: No
article_type: original
author:
- first_name: Stefano
full_name: Mazzanti, Stefano
last_name: Mazzanti
- first_name: Bogdan
full_name: Kurpil, Bogdan
last_name: Kurpil
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
- first_name: Markus
full_name: Antonietti, Markus
last_name: Antonietti
- first_name: Aleksandr
full_name: Savateev, Aleksandr
last_name: Savateev
citation:
ama: Mazzanti S, Kurpil B, Pieber B, Antonietti M, Savateev A. Dichloromethylation
of enones by carbon nitride photocatalysis. Nature Communications. 2020;11.
doi:10.1038/s41467-020-15131-0
apa: Mazzanti, S., Kurpil, B., Pieber, B., Antonietti, M., & Savateev, A. (2020).
Dichloromethylation of enones by carbon nitride photocatalysis. Nature Communications.
Springer Nature. https://doi.org/10.1038/s41467-020-15131-0
chicago: Mazzanti, Stefano, Bogdan Kurpil, Bartholomäus Pieber, Markus Antonietti,
and Aleksandr Savateev. “Dichloromethylation of Enones by Carbon Nitride Photocatalysis.”
Nature Communications. Springer Nature, 2020. https://doi.org/10.1038/s41467-020-15131-0.
ieee: S. Mazzanti, B. Kurpil, B. Pieber, M. Antonietti, and A. Savateev, “Dichloromethylation
of enones by carbon nitride photocatalysis,” Nature Communications, vol.
11. Springer Nature, 2020.
ista: Mazzanti S, Kurpil B, Pieber B, Antonietti M, Savateev A. 2020. Dichloromethylation
of enones by carbon nitride photocatalysis. Nature Communications. 11, 1387.
mla: Mazzanti, Stefano, et al. “Dichloromethylation of Enones by Carbon Nitride
Photocatalysis.” Nature Communications, vol. 11, 1387, Springer Nature,
2020, doi:10.1038/s41467-020-15131-0.
short: S. Mazzanti, B. Kurpil, B. Pieber, M. Antonietti, A. Savateev, Nature Communications
11 (2020).
date_created: 2022-08-25T11:10:15Z
date_published: 2020-03-13T00:00:00Z
date_updated: 2023-02-21T10:10:14Z
day: '13'
doi: 10.1038/s41467-020-15131-0
extern: '1'
intvolume: ' 11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1038/s41467-020-15131-0
month: '03'
oa: 1
oa_version: Published Version
publication: Nature Communications
publication_identifier:
eissn:
- 2041-1723
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dichloromethylation of enones by carbon nitride photocatalysis
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2020'
...
---
_id: '11986'
abstract:
- lang: eng
text: Carbon nitride materials have emerged as an efficient and sustainable class
of heterogeneous photocatalysts, particularly when paired with nickel in dual
catalytic cross-coupling reactions. Performing these transformations on larger
scales using a continuous process is difficult due to the problems associated
with handling solids in flow. By combining an oscillatory pump with a microstructured
plug flow photoreactor, a stable suspension of the photocatalyst can be maintained,
circumventing clogging of the reactor channels. Through careful tuning of the
oscillator properties, the residence time distribution (RTD) was optimized, whilst
maintaining a stable catalyst suspension. Short residence times (20 min) were
achieved using optimized conditions and the recyclability of the photocatalyst
was demonstrated over 10 cycles with no loss of activity. During a stable 4.5
hour scale-out demonstration, the model substrate could be isolated on 12 g scale
(90% yield, 2.67 g h−1). Moreover, the method was applied for the gram scale synthesis
of an intermediate of the active pharmaceutical ingredient tetracaine.
article_processing_charge: No
article_type: original
author:
- first_name: Cristian
full_name: Rosso, Cristian
last_name: Rosso
- first_name: Sebastian
full_name: Gisbertz, Sebastian
last_name: Gisbertz
- first_name: Jason D.
full_name: Williams, Jason D.
last_name: Williams
- first_name: Hannes P. L.
full_name: Gemoets, Hannes P. L.
last_name: Gemoets
- first_name: Wouter
full_name: Debrouwer, Wouter
last_name: Debrouwer
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
- first_name: C. Oliver
full_name: Kappe, C. Oliver
last_name: Kappe
citation:
ama: Rosso C, Gisbertz S, Williams JD, et al. An oscillatory plug flow photoreactor
facilitates semi-heterogeneous dual nickel/carbon nitride photocatalytic C–N couplings.
Reaction Chemistry and Engineering. 2020;5(3):597-604. doi:10.1039/d0re00036a
apa: Rosso, C., Gisbertz, S., Williams, J. D., Gemoets, H. P. L., Debrouwer, W.,
Pieber, B., & Kappe, C. O. (2020). An oscillatory plug flow photoreactor facilitates
semi-heterogeneous dual nickel/carbon nitride photocatalytic C–N couplings. Reaction
Chemistry and Engineering. Royal Society of Chemistry. https://doi.org/10.1039/d0re00036a
chicago: Rosso, Cristian, Sebastian Gisbertz, Jason D. Williams, Hannes P. L. Gemoets,
Wouter Debrouwer, Bartholomäus Pieber, and C. Oliver Kappe. “An Oscillatory Plug
Flow Photoreactor Facilitates Semi-Heterogeneous Dual Nickel/Carbon Nitride Photocatalytic
C–N Couplings.” Reaction Chemistry and Engineering. Royal Society of Chemistry,
2020. https://doi.org/10.1039/d0re00036a.
ieee: C. Rosso et al., “An oscillatory plug flow photoreactor facilitates
semi-heterogeneous dual nickel/carbon nitride photocatalytic C–N couplings,” Reaction
Chemistry and Engineering, vol. 5, no. 3. Royal Society of Chemistry, pp.
597–604, 2020.
ista: Rosso C, Gisbertz S, Williams JD, Gemoets HPL, Debrouwer W, Pieber B, Kappe
CO. 2020. An oscillatory plug flow photoreactor facilitates semi-heterogeneous
dual nickel/carbon nitride photocatalytic C–N couplings. Reaction Chemistry and
Engineering. 5(3), 597–604.
mla: Rosso, Cristian, et al. “An Oscillatory Plug Flow Photoreactor Facilitates
Semi-Heterogeneous Dual Nickel/Carbon Nitride Photocatalytic C–N Couplings.” Reaction
Chemistry and Engineering, vol. 5, no. 3, Royal Society of Chemistry, 2020,
pp. 597–604, doi:10.1039/d0re00036a.
short: C. Rosso, S. Gisbertz, J.D. Williams, H.P.L. Gemoets, W. Debrouwer, B. Pieber,
C.O. Kappe, Reaction Chemistry and Engineering 5 (2020) 597–604.
date_created: 2022-08-25T11:45:02Z
date_published: 2020-03-01T00:00:00Z
date_updated: 2023-02-21T10:10:28Z
day: '01'
doi: 10.1039/d0re00036a
extern: '1'
intvolume: ' 5'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1039/D0RE00036A
month: '03'
oa: 1
oa_version: Published Version
page: 597-604
publication: Reaction Chemistry and Engineering
publication_identifier:
eissn:
- 2058-9883
publication_status: published
publisher: Royal Society of Chemistry
quality_controlled: '1'
scopus_import: '1'
status: public
title: An oscillatory plug flow photoreactor facilitates semi-heterogeneous dual nickel/carbon
nitride photocatalytic C–N couplings
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2020'
...
---
_id: '12188'
abstract:
- lang: eng
text: Molecular mechanisms enabling the switching and maintenance of epigenetic
states are not fully understood. Distinct histone modifications are often associated
with ON/OFF epigenetic states, but how these states are stably maintained through
DNA replication, yet in certain situations switch from one to another remains
unclear. Here, we address this problem through identification of Arabidopsis INCURVATA11
(ICU11) as a Polycomb Repressive Complex 2 accessory protein. ICU11 robustly immunoprecipitated
in vivo with PRC2 core components and the accessory proteins, EMBRYONIC FLOWER
1 (EMF1), LIKE HETEROCHROMATIN PROTEIN1 (LHP1), and TELOMERE_REPEAT_BINDING FACTORS
(TRBs). ICU11 encodes a 2-oxoglutarate-dependent dioxygenase, an activity associated
with histone demethylation in other organisms, and mutant plants show defects
in multiple aspects of the Arabidopsis epigenome. To investigate its primary molecular
function we identified the Arabidopsis FLOWERING LOCUS C (FLC) as a direct target
and found icu11 disrupted the cold-induced, Polycomb-mediated silencing underlying
vernalization. icu11 prevented reduction in H3K36me3 levels normally seen during
the early cold phase, supporting a role for ICU11 in H3K36me3 demethylation. This
was coincident with an attenuation of H3K27me3 at the internal nucleation site
in FLC, and reduction in H3K27me3 levels across the body of the gene after plants
were returned to the warm. Thus, ICU11 is required for the cold-induced epigenetic
switching between the mutually exclusive chromatin states at FLC, from the active
H3K36me3 state to the silenced H3K27me3 state. These data support the importance
of physical coupling of histone modification activities to promote epigenetic
switching between opposing chromatin states.
acknowledgement: We would like to thank Scott Berry for help with ICU-GFP nuclear
localization microscopy, Hao Yu and Lisha Shen for assistance with 6mA DNA methylation
analysis, Donna Gibson for graphic design assistance, and members of the C.D. and
Howard laboratories for helpful discussions. This work was funded by the European
Research Council grants to “MEXTIM” (to C.D.) and “SexMeth” (to X. Feng), by the
Biotechnological and Biological Sciences Research Council (BBSRC) Institute Strategic
Programmes GRO (BB/J004588/1), GEN (BB/P013511/1), BBSRC grant (to X. Feng) (BB/S009620/1),
and the Marie Sklodowska–Curie Postdoctoral Fellowships “UNRAVEL” (to R.H.B.) and
"WISDOM" (to X. Fang). Additional funding via the Wellcome Trust through a Senior
Research Fellowship (to J.R.) (103139) and a multiuser equipment grant (108504).
The Wellcome Centre for Cell Biology is supported by core funding from the Wellcome
Trust (203149).
article_processing_charge: No
article_type: original
author:
- first_name: Rebecca H.
full_name: Bloomer, Rebecca H.
last_name: Bloomer
- first_name: Claire E.
full_name: Hutchison, Claire E.
last_name: Hutchison
- first_name: Isabel
full_name: Bäurle, Isabel
last_name: Bäurle
- first_name: James
full_name: Walker, James
last_name: Walker
- first_name: Xiaofeng
full_name: Fang, Xiaofeng
last_name: Fang
- first_name: Pumi
full_name: Perera, Pumi
last_name: Perera
- first_name: Christos N.
full_name: Velanis, Christos N.
last_name: Velanis
- first_name: Serin
full_name: Gümüs, Serin
last_name: Gümüs
- first_name: Christos
full_name: Spanos, Christos
last_name: Spanos
- first_name: Juri
full_name: Rappsilber, Juri
last_name: Rappsilber
- first_name: Xiaoqi
full_name: Feng, Xiaoqi
id: e0164712-22ee-11ed-b12a-d80fcdf35958
last_name: Feng
orcid: 0000-0002-4008-1234
- first_name: Justin
full_name: Goodrich, Justin
last_name: Goodrich
- first_name: Caroline
full_name: Dean, Caroline
last_name: Dean
citation:
ama: Bloomer RH, Hutchison CE, Bäurle I, et al. The Arabidopsis epigenetic regulator
ICU11 as an accessory protein of polycomb repressive complex 2. Proceedings
of the National Academy of Sciences. 2020;117(28):16660-16666. doi:10.1073/pnas.1920621117
apa: Bloomer, R. H., Hutchison, C. E., Bäurle, I., Walker, J., Fang, X., Perera,
P., … Dean, C. (2020). The Arabidopsis epigenetic regulator ICU11 as an accessory
protein of polycomb repressive complex 2. Proceedings of the National Academy
of Sciences. Proceedings of the National Academy of Sciences. https://doi.org/10.1073/pnas.1920621117
chicago: Bloomer, Rebecca H., Claire E. Hutchison, Isabel Bäurle, James Walker,
Xiaofeng Fang, Pumi Perera, Christos N. Velanis, et al. “The Arabidopsis Epigenetic
Regulator ICU11 as an Accessory Protein of Polycomb Repressive Complex 2.” Proceedings
of the National Academy of Sciences. Proceedings of the National Academy of
Sciences, 2020. https://doi.org/10.1073/pnas.1920621117.
ieee: R. H. Bloomer et al., “The Arabidopsis epigenetic regulator ICU11
as an accessory protein of polycomb repressive complex 2,” Proceedings of the
National Academy of Sciences, vol. 117, no. 28. Proceedings of the National
Academy of Sciences, pp. 16660–16666, 2020.
ista: Bloomer RH, Hutchison CE, Bäurle I, Walker J, Fang X, Perera P, Velanis CN,
Gümüs S, Spanos C, Rappsilber J, Feng X, Goodrich J, Dean C. 2020. The Arabidopsis
epigenetic regulator ICU11 as an accessory protein of polycomb repressive complex
2. Proceedings of the National Academy of Sciences. 117(28), 16660–16666.
mla: Bloomer, Rebecca H., et al. “The Arabidopsis Epigenetic Regulator ICU11 as
an Accessory Protein of Polycomb Repressive Complex 2.” Proceedings of the
National Academy of Sciences, vol. 117, no. 28, Proceedings of the National
Academy of Sciences, 2020, pp. 16660–66, doi:10.1073/pnas.1920621117.
short: R.H. Bloomer, C.E. Hutchison, I. Bäurle, J. Walker, X. Fang, P. Perera, C.N.
Velanis, S. Gümüs, C. Spanos, J. Rappsilber, X. Feng, J. Goodrich, C. Dean, Proceedings
of the National Academy of Sciences 117 (2020) 16660–16666.
date_created: 2023-01-16T09:15:44Z
date_published: 2020-05-22T00:00:00Z
date_updated: 2023-05-08T10:53:55Z
day: '22'
ddc:
- '580'
department:
- _id: XiFe
doi: 10.1073/pnas.1920621117
extern: '1'
external_id:
pmid:
- '32601198'
file:
- access_level: open_access
checksum: cedee184cb12f454f2fba4158ff47db9
content_type: application/pdf
creator: alisjak
date_created: 2023-02-07T11:29:55Z
date_updated: 2023-02-07T11:29:55Z
file_id: '12526'
file_name: 2020_PNAS_Bloomer.pdf
file_size: 1105414
relation: main_file
success: 1
file_date_updated: 2023-02-07T11:29:55Z
has_accepted_license: '1'
intvolume: ' 117'
issue: '28'
keyword:
- Multidisciplinary
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7368280/
month: '05'
oa: 1
oa_version: Published Version
page: 16660-16666
pmid: 1
publication: Proceedings of the National Academy of Sciences
publication_identifier:
issn:
- 0027-8424
- 1091-6490
publication_status: published
publisher: Proceedings of the National Academy of Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Arabidopsis epigenetic regulator ICU11 as an accessory protein of polycomb
repressive complex 2
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 117
year: '2020'
...
---
_id: '12189'
abstract:
- lang: eng
text: Meiotic crossovers (COs) are important for reshuffling genetic information
between homologous chromosomes and they are essential for their correct segregation.
COs are unevenly distributed along chromosomes and the underlying mechanisms controlling
CO localization are not well understood. We previously showed that meiotic COs
are mis-localized in the absence of AXR1, an enzyme involved in the neddylation/rubylation
protein modification pathway in Arabidopsis thaliana. Here, we report that in
axr1-/-, male meiocytes show a strong defect in chromosome pairing whereas the
formation of the telomere bouquet is not affected. COs are also redistributed
towards subtelomeric chromosomal ends where they frequently form clusters, in
contrast to large central regions depleted in recombination. The CO suppressed
regions correlate with DNA hypermethylation of transposable elements (TEs) in
the CHH context in axr1-/- meiocytes. Through examining somatic methylomes, we
found axr1-/- affects DNA methylation in a plant, causing hypermethylation in
all sequence contexts (CG, CHG and CHH) in TEs. Impairment of the main pathways
involved in DNA methylation is epistatic over axr1-/- for DNA methylation in somatic
cells but does not restore regular chromosome segregation during meiosis. Collectively,
our findings reveal that the neddylation pathway not only regulates hormonal perception
and CO distribution but is also, directly or indirectly, a major limiting pathway
of TE DNA methylation in somatic cells.
acknowledgement: The authors wish to thank Cécile Raynaud, Eric Jenczewski, Rajeev
Kumar, Raphaël Mercier and Jean Molinier for critical reading of the manuscript.
article_number: e1008894
article_processing_charge: No
article_type: original
author:
- first_name: Nicolas
full_name: Christophorou, Nicolas
last_name: Christophorou
- first_name: Wenjing
full_name: She, Wenjing
last_name: She
- first_name: Jincheng
full_name: Long, Jincheng
last_name: Long
- first_name: Aurélie
full_name: Hurel, Aurélie
last_name: Hurel
- first_name: Sébastien
full_name: Beaubiat, Sébastien
last_name: Beaubiat
- first_name: Yassir
full_name: Idir, Yassir
last_name: Idir
- first_name: Marina
full_name: Tagliaro-Jahns, Marina
last_name: Tagliaro-Jahns
- first_name: Aurélie
full_name: Chambon, Aurélie
last_name: Chambon
- first_name: Victor
full_name: Solier, Victor
last_name: Solier
- first_name: Daniel
full_name: Vezon, Daniel
last_name: Vezon
- first_name: Mathilde
full_name: Grelon, Mathilde
last_name: Grelon
- first_name: Xiaoqi
full_name: Feng, Xiaoqi
id: e0164712-22ee-11ed-b12a-d80fcdf35958
last_name: Feng
orcid: 0000-0002-4008-1234
- first_name: Nicolas
full_name: Bouché, Nicolas
last_name: Bouché
- first_name: Christine
full_name: Mézard, Christine
last_name: Mézard
citation:
ama: Christophorou N, She W, Long J, et al. AXR1 affects DNA methylation independently
of its role in regulating meiotic crossover localization. PLOS Genetics.
2020;16(6). doi:10.1371/journal.pgen.1008894
apa: Christophorou, N., She, W., Long, J., Hurel, A., Beaubiat, S., Idir, Y., …
Mézard, C. (2020). AXR1 affects DNA methylation independently of its role in regulating
meiotic crossover localization. PLOS Genetics. Public Library of Science
(PLoS). https://doi.org/10.1371/journal.pgen.1008894
chicago: Christophorou, Nicolas, Wenjing She, Jincheng Long, Aurélie Hurel, Sébastien
Beaubiat, Yassir Idir, Marina Tagliaro-Jahns, et al. “AXR1 Affects DNA Methylation
Independently of Its Role in Regulating Meiotic Crossover Localization.” PLOS
Genetics. Public Library of Science (PLoS), 2020. https://doi.org/10.1371/journal.pgen.1008894.
ieee: N. Christophorou et al., “AXR1 affects DNA methylation independently
of its role in regulating meiotic crossover localization,” PLOS Genetics,
vol. 16, no. 6. Public Library of Science (PLoS), 2020.
ista: Christophorou N, She W, Long J, Hurel A, Beaubiat S, Idir Y, Tagliaro-Jahns
M, Chambon A, Solier V, Vezon D, Grelon M, Feng X, Bouché N, Mézard C. 2020. AXR1
affects DNA methylation independently of its role in regulating meiotic crossover
localization. PLOS Genetics. 16(6), e1008894.
mla: Christophorou, Nicolas, et al. “AXR1 Affects DNA Methylation Independently
of Its Role in Regulating Meiotic Crossover Localization.” PLOS Genetics,
vol. 16, no. 6, e1008894, Public Library of Science (PLoS), 2020, doi:10.1371/journal.pgen.1008894.
short: N. Christophorou, W. She, J. Long, A. Hurel, S. Beaubiat, Y. Idir, M. Tagliaro-Jahns,
A. Chambon, V. Solier, D. Vezon, M. Grelon, X. Feng, N. Bouché, C. Mézard, PLOS
Genetics 16 (2020).
date_created: 2023-01-16T09:16:10Z
date_published: 2020-06-29T00:00:00Z
date_updated: 2023-05-08T10:54:39Z
day: '29'
department:
- _id: XiFe
doi: 10.1371/journal.pgen.1008894
extern: '1'
external_id:
pmid:
- '32598340'
intvolume: ' 16'
issue: '6'
keyword:
- Cancer Research
- Genetics (clinical)
- Genetics
- Molecular Biology
- Ecology
- Evolution
- Behavior and Systematics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7351236/
month: '06'
oa: 1
oa_version: Published Version
pmid: 1
publication: PLOS Genetics
publication_identifier:
issn:
- 1553-7404
publication_status: published
publisher: Public Library of Science (PLoS)
quality_controlled: '1'
scopus_import: '1'
status: public
title: AXR1 affects DNA methylation independently of its role in regulating meiotic
crossover localization
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2020'
...
---
_id: '12310'
abstract:
- lang: eng
text: Let be a sequence of points on an elliptic curve defined over a number field
K. In this paper, we study the denominators of the x-coordinates of this sequence.
We prove that, if Q is a torsion point of prime order, then for n large enough
there always exists a primitive divisor. Later on, we show the link between the
study of the primitive divisors and a Lang-Trotter conjecture. Indeed, given two
points P and Q on the elliptic curve, we prove a lower bound for the number of
primes p such that P is in the orbit of Q modulo p.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matteo
full_name: Verzobio, Matteo
id: 7aa8f170-131e-11ed-88e1-a9efd01027cb
last_name: Verzobio
orcid: 0000-0002-0854-0306
citation:
ama: Verzobio M. Primitive divisors of sequences associated to elliptic curves.
Journal of Number Theory. 2020;209(4):378-390. doi:10.1016/j.jnt.2019.09.003
apa: Verzobio, M. (2020). Primitive divisors of sequences associated to elliptic
curves. Journal of Number Theory. Elsevier. https://doi.org/10.1016/j.jnt.2019.09.003
chicago: Verzobio, Matteo. “Primitive Divisors of Sequences Associated to Elliptic
Curves.” Journal of Number Theory. Elsevier, 2020. https://doi.org/10.1016/j.jnt.2019.09.003.
ieee: M. Verzobio, “Primitive divisors of sequences associated to elliptic curves,”
Journal of Number Theory, vol. 209, no. 4. Elsevier, pp. 378–390, 2020.
ista: Verzobio M. 2020. Primitive divisors of sequences associated to elliptic curves.
Journal of Number Theory. 209(4), 378–390.
mla: Verzobio, Matteo. “Primitive Divisors of Sequences Associated to Elliptic Curves.”
Journal of Number Theory, vol. 209, no. 4, Elsevier, 2020, pp. 378–90,
doi:10.1016/j.jnt.2019.09.003.
short: M. Verzobio, Journal of Number Theory 209 (2020) 378–390.
date_created: 2023-01-16T11:45:07Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2023-05-10T11:14:56Z
day: '01'
doi: 10.1016/j.jnt.2019.09.003
extern: '1'
external_id:
arxiv:
- '1906.00632'
intvolume: ' 209'
issue: '4'
keyword:
- Algebra and Number Theory
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1906.00632
month: '04'
oa: 1
oa_version: Preprint
page: 378-390
publication: Journal of Number Theory
publication_identifier:
issn:
- 0022-314X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Primitive divisors of sequences associated to elliptic curves
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 209
year: '2020'
...
---
_id: '12594'
abstract:
- lang: eng
text: Information about end-of-winter spatial distribution of snow depth is important
for seasonal forecasts of spring/summer streamflow in high-mountain regions. Nevertheless,
such information typically relies upon extrapolation from a sparse network of
observations at low elevations. Here, we test the potential of high-resolution
snow depth data derived from optical stereophotogrammetry of Pléiades satellites
for improving the representation of snow depth initial conditions (SDICs) in a
glacio-hydrological model and assess potential improvements in the skill of snowmelt
and streamflow simulations in a high-elevation Andean catchment. We calibrate
model parameters controlling glacier mass balance and snow cover evolution using
ground-based and satellite observations, and consider the relative importance
of accurate estimates of SDICs compared to model parameters and forcings. We find
that Pléiades SDICs improve the simulation of snow-covered area, glacier mass
balance, and monthly streamflow compared to alternative SDICs based upon extrapolation
of meteorological variables or statistical methods to estimate SDICs based upon
topography. Model simulations are found to be sensitive to SDICs in the early
spring (up to 48% variability in modeled streamflow compared to the best estimate
model), and to temperature gradients in all months that control albedo and melt
rates over a large elevation range (>2,400 m). As such, appropriately characterizing
the distribution of total snow volume with elevation is important for reproducing
total streamflow and the proportions of snowmelt. Therefore, optical stereo-photogrammetry
offers an advantage for obtaining SDICs that aid both the timing and magnitude
of streamflow simulations, process representation (e.g., snow cover evolution)
and has the potential for large spatial domains.
article_number: e2020WR027188
article_processing_charge: No
article_type: original
author:
- first_name: Thomas E.
full_name: Shaw, Thomas E.
last_name: Shaw
- first_name: Alexis
full_name: Caro, Alexis
last_name: Caro
- first_name: Pablo
full_name: Mendoza, Pablo
last_name: Mendoza
- first_name: Álvaro
full_name: Ayala, Álvaro
last_name: Ayala
- first_name: Francesca
full_name: Pellicciotti, Francesca
id: b28f055a-81ea-11ed-b70c-a9fe7f7b0e70
last_name: Pellicciotti
- first_name: Simon
full_name: Gascoin, Simon
last_name: Gascoin
- first_name: James
full_name: McPhee, James
last_name: McPhee
citation:
ama: Shaw TE, Caro A, Mendoza P, et al. The utility of optical satellite winter
snow depths for initializing a glacio‐hydrological model of a High‐Elevation,
Andean catchment. Water Resources Research. 2020;56(8). doi:10.1029/2020wr027188
apa: Shaw, T. E., Caro, A., Mendoza, P., Ayala, Á., Pellicciotti, F., Gascoin, S.,
& McPhee, J. (2020). The utility of optical satellite winter snow depths for
initializing a glacio‐hydrological model of a High‐Elevation, Andean catchment.
Water Resources Research. American Geophysical Union. https://doi.org/10.1029/2020wr027188
chicago: Shaw, Thomas E., Alexis Caro, Pablo Mendoza, Álvaro Ayala, Francesca Pellicciotti,
Simon Gascoin, and James McPhee. “The Utility of Optical Satellite Winter Snow
Depths for Initializing a Glacio‐hydrological Model of a High‐Elevation, Andean
Catchment.” Water Resources Research. American Geophysical Union, 2020.
https://doi.org/10.1029/2020wr027188.
ieee: T. E. Shaw et al., “The utility of optical satellite winter snow depths
for initializing a glacio‐hydrological model of a High‐Elevation, Andean catchment,”
Water Resources Research, vol. 56, no. 8. American Geophysical Union, 2020.
ista: Shaw TE, Caro A, Mendoza P, Ayala Á, Pellicciotti F, Gascoin S, McPhee J.
2020. The utility of optical satellite winter snow depths for initializing a glacio‐hydrological
model of a High‐Elevation, Andean catchment. Water Resources Research. 56(8),
e2020WR027188.
mla: Shaw, Thomas E., et al. “The Utility of Optical Satellite Winter Snow Depths
for Initializing a Glacio‐hydrological Model of a High‐Elevation, Andean Catchment.”
Water Resources Research, vol. 56, no. 8, e2020WR027188, American Geophysical
Union, 2020, doi:10.1029/2020wr027188.
short: T.E. Shaw, A. Caro, P. Mendoza, Á. Ayala, F. Pellicciotti, S. Gascoin, J.
McPhee, Water Resources Research 56 (2020).
date_created: 2023-02-20T08:12:22Z
date_published: 2020-08-01T00:00:00Z
date_updated: 2023-02-28T12:41:45Z
day: '01'
doi: 10.1029/2020wr027188
extern: '1'
intvolume: ' 56'
issue: '8'
keyword:
- Water Science and Technology
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1029/2020WR027188
month: '08'
oa: 1
oa_version: Published Version
publication: Water Resources Research
publication_identifier:
eissn:
- 1944-7973
issn:
- 0043-1397
publication_status: published
publisher: American Geophysical Union
quality_controlled: '1'
scopus_import: '1'
status: public
title: The utility of optical satellite winter snow depths for initializing a glacio‐hydrological
model of a High‐Elevation, Andean catchment
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2020'
...
---
_id: '12595'
abstract:
- lang: eng
text: The seasonal dynamic changes of Tibetan glaciers have seen little prior investigation,
despite the increase in geodetic studies of multi-year changes. This study compares
seasonal glacier dynamics (“cold” and “warm” seasons) in the ablation zone of
Parlung No. 4 Glacier, a temperate glacier in the monsoon-influenced southeastern
Tibetan Plateau, by using repeat unpiloted aerial vehicle (UAV) surveys combined
with Structure-from-Motion (SfM) photogrammetry and ground stake measurements.
Our results showed that the surveyed ablation zone had a mean change of −2.7 m
of ice surface elevation during the period of September 2018 to October 2019 but
is characterized by significant seasonal cyclic variations with ice surface elevation
lifting (+2.0 m) in the cold season (September 2018 to June 2019) but lowering
(−4.7 m) in the warm season (June 2019 to October 2019). Over an annual timescale,
surface lowering was greatly suppressed by the resupply of ice from the glacier’s
accumulation area—the annual emergence velocity compensates for about 55% of surface
ablation in our study area. Cold season emergence velocities (3.0 ± 1.2 m) were
~5-times larger than those observed in the warm season (0.6 ± 1.0 m). Distinct
spring precipitation patterns may contribute to these distinct seasonal signals.
Such seasonal dynamic conditions are possibly critical for different glacier responses
to climate change in this region of the Tibetan Plateau, and perhaps further afield.
article_number: '2389'
article_processing_charge: No
article_type: original
author:
- first_name: Wei
full_name: Yang, Wei
last_name: Yang
- first_name: Chuanxi
full_name: Zhao, Chuanxi
last_name: Zhao
- first_name: Matthew
full_name: Westoby, Matthew
last_name: Westoby
- first_name: Tandong
full_name: Yao, Tandong
last_name: Yao
- first_name: Yongjie
full_name: Wang, Yongjie
last_name: Wang
- first_name: Francesca
full_name: Pellicciotti, Francesca
id: b28f055a-81ea-11ed-b70c-a9fe7f7b0e70
last_name: Pellicciotti
- first_name: Jianmin
full_name: Zhou, Jianmin
last_name: Zhou
- first_name: Zhen
full_name: He, Zhen
last_name: He
- first_name: Evan
full_name: Miles, Evan
last_name: Miles
citation:
ama: Yang W, Zhao C, Westoby M, et al. Seasonal dynamics of a temperate Tibetan
glacier revealed by high-resolution UAV photogrammetry and in situ measurements.
Remote Sensing. 2020;12(15). doi:10.3390/rs12152389
apa: Yang, W., Zhao, C., Westoby, M., Yao, T., Wang, Y., Pellicciotti, F., … Miles,
E. (2020). Seasonal dynamics of a temperate Tibetan glacier revealed by high-resolution
UAV photogrammetry and in situ measurements. Remote Sensing. MDPI. https://doi.org/10.3390/rs12152389
chicago: Yang, Wei, Chuanxi Zhao, Matthew Westoby, Tandong Yao, Yongjie Wang, Francesca
Pellicciotti, Jianmin Zhou, Zhen He, and Evan Miles. “Seasonal Dynamics of a Temperate
Tibetan Glacier Revealed by High-Resolution UAV Photogrammetry and in Situ Measurements.”
Remote Sensing. MDPI, 2020. https://doi.org/10.3390/rs12152389.
ieee: W. Yang et al., “Seasonal dynamics of a temperate Tibetan glacier revealed
by high-resolution UAV photogrammetry and in situ measurements,” Remote Sensing,
vol. 12, no. 15. MDPI, 2020.
ista: Yang W, Zhao C, Westoby M, Yao T, Wang Y, Pellicciotti F, Zhou J, He Z, Miles
E. 2020. Seasonal dynamics of a temperate Tibetan glacier revealed by high-resolution
UAV photogrammetry and in situ measurements. Remote Sensing. 12(15), 2389.
mla: Yang, Wei, et al. “Seasonal Dynamics of a Temperate Tibetan Glacier Revealed
by High-Resolution UAV Photogrammetry and in Situ Measurements.” Remote Sensing,
vol. 12, no. 15, 2389, MDPI, 2020, doi:10.3390/rs12152389.
short: W. Yang, C. Zhao, M. Westoby, T. Yao, Y. Wang, F. Pellicciotti, J. Zhou,
Z. He, E. Miles, Remote Sensing 12 (2020).
date_created: 2023-02-20T08:12:29Z
date_published: 2020-07-24T00:00:00Z
date_updated: 2023-02-28T12:36:22Z
day: '24'
doi: 10.3390/rs12152389
extern: '1'
intvolume: ' 12'
issue: '15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.3390/rs12152389
month: '07'
oa: 1
oa_version: Published Version
publication: Remote Sensing
publication_identifier:
issn:
- 2072-4292
publication_status: published
publisher: MDPI
quality_controlled: '1'
scopus_import: '1'
status: public
title: Seasonal dynamics of a temperate Tibetan glacier revealed by high-resolution
UAV photogrammetry and in situ measurements
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2020'
...