[{"day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1512.08148"}],"external_id":{"arxiv":["1512.08148"]},"extern":"1","oa":1,"status":"public","related_material":{"record":[{"status":"public","id":"11855","relation":"earlier_version"}]},"intvolume":"        65","date_published":"2018-12-01T00:00:00Z","doi":"10.1145/3218657","quality_controlled":"1","arxiv":1,"month":"12","publication":"Journal of the ACM","date_created":"2022-08-08T12:33:17Z","oa_version":"Preprint","citation":{"ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” <i>Journal of the ACM</i>, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40, 2018.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, Journal of the ACM 65 (2018) 1–40.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>Journal of the ACM</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3218657\">https://doi.org/10.1145/3218657</a>.","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 65(6), 1–40.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. <i>Journal of the ACM</i>. 2018;65(6):1-40. doi:<a href=\"https://doi.org/10.1145/3218657\">10.1145/3218657</a>","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2018). Decremental single-source shortest paths on undirected graphs in near-linear total update time. <i>Journal of the ACM</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3218657\">https://doi.org/10.1145/3218657</a>","mla":"Henzinger, Monika H., et al. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>Journal of the ACM</i>, vol. 65, no. 6, Association for Computing Machinery, 2018, pp. 1–40, doi:<a href=\"https://doi.org/10.1145/3218657\">10.1145/3218657</a>."},"type":"journal_article","title":"Decremental single-source shortest paths on undirected graphs in near-linear total update time","page":"1-40","publication_status":"published","article_type":"original","publisher":"Association for Computing Machinery","_id":"11768","date_updated":"2023-02-21T16:30:41Z","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary.\r\n\r\nIn contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.","lang":"eng"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]},"author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"first_name":"Sebastian","full_name":"Krinninger, Sebastian","last_name":"Krinninger"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"year":"2018","issue":"6","scopus_import":"1","volume":65},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"11827","publication_status":"published","title":"A tree structure for dynamic facility location","alternative_title":["LIPIcs"],"volume":112,"scopus_import":"1","year":"2018","language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959770811"]},"author":[{"first_name":"Gramoz ","full_name":"Goranci, Gramoz ","last_name":"Goranci"},{"full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Leniowski, Dariusz","last_name":"Leniowski","first_name":"Dariusz"}],"conference":{"location":"Helsinki, Finland","start_date":"2018-08-20","name":"ESA: Annual European Symposium on Algorithms","end_date":"2018-08-22"},"article_processing_charge":"No","date_updated":"2023-02-16T10:50:51Z","abstract":[{"lang":"eng","text":"We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2018-08-14T00:00:00Z","doi":"10.4230/LIPICS.ESA.2018.39","intvolume":"       112","article_number":"39","status":"public","external_id":{"arxiv":["1909.06653"]},"extern":"1","day":"14","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2018.39"}],"oa":1,"type":"conference","publication":"26th Annual European Symposium on Algorithms","citation":{"ama":"Goranci G, Henzinger MH, Leniowski D. A tree structure for dynamic facility location. In: <i>26th Annual European Symposium on Algorithms</i>. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">10.4230/LIPICS.ESA.2018.39</a>","mla":"Goranci, Gramoz, et al. “A Tree Structure for Dynamic Facility Location.” <i>26th Annual European Symposium on Algorithms</i>, vol. 112, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">10.4230/LIPICS.ESA.2018.39</a>.","apa":"Goranci, G., Henzinger, M. H., &#38; Leniowski, D. (2018). A tree structure for dynamic facility location. In <i>26th Annual European Symposium on Algorithms</i> (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">https://doi.org/10.4230/LIPICS.ESA.2018.39</a>","short":"G. Goranci, M.H. Henzinger, D. Leniowski, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ieee":"G. Goranci, M. H. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in <i>26th Annual European Symposium on Algorithms</i>, Helsinki, Finland, 2018, vol. 112.","chicago":"Goranci, Gramoz , Monika H Henzinger, and Dariusz Leniowski. “A Tree Structure for Dynamic Facility Location.” In <i>26th Annual European Symposium on Algorithms</i>, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">https://doi.org/10.4230/LIPICS.ESA.2018.39</a>.","ista":"Goranci G, Henzinger MH, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39."},"oa_version":"Published Version","date_created":"2022-08-12T08:20:57Z","arxiv":1,"month":"08","quality_controlled":"1"},{"type":"conference","date_created":"2022-08-12T08:26:42Z","citation":{"ista":"Goranci G, Henzinger MH, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” In <i>26th Annual European Symposium on Algorithms</i>, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>.","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in <i>26th Annual European Symposium on Algorithms</i>, Helsinki, Finland, 2018, vol. 112.","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","mla":"Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” <i>26th Annual European Symposium on Algorithms</i>, vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">10.4230/LIPICS.ESA.2018.40</a>.","apa":"Goranci, G., Henzinger, M. H., &#38; Peng, P. (2018). Dynamic effective resistances and approximate schur complement on separable graphs. In <i>26th Annual European Symposium on Algorithms</i> (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>","ama":"Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate schur complement on separable graphs. In: <i>26th Annual European Symposium on Algorithms</i>. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">10.4230/LIPICS.ESA.2018.40</a>"},"oa_version":"Published Version","publication":"26th Annual European Symposium on Algorithms","month":"08","arxiv":1,"quality_controlled":"1","article_number":"40","intvolume":"       112","date_published":"2018-08-14T00:00:00Z","doi":"10.4230/LIPICS.ESA.2018.40","status":"public","oa":1,"day":"14","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2018.40","open_access":"1"}],"extern":"1","external_id":{"arxiv":["1802.09111"]},"volume":112,"year":"2018","scopus_import":"1","author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"first_name":"Pan","full_name":"Peng, Pan","last_name":"Peng"}],"publication_identifier":{"isbn":["9783959770811"],"issn":["1868-8969"]},"conference":{"name":"ESA: Annual European Symposium on Algorithms","location":"Helsinki, Finland","start_date":"2018-08-20","end_date":"2018-08-22"},"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest.\r\nWe complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false.\r\nWe further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false.","lang":"eng"}],"date_updated":"2023-02-16T11:08:08Z","article_processing_charge":"No","_id":"11828","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","title":"Dynamic effective resistances and approximate schur complement on separable graphs","alternative_title":["LIPIcs"]},{"page":"1 - 20","title":"Dynamic algorithms for graph coloring","publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","_id":"11872","article_processing_charge":"No","date_updated":"2023-02-17T11:39:01Z","abstract":[{"text":"We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with  worst-case update time [4].","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"conference":{"start_date":"2018-01-07","name":"SODA: Symposium on Discrete Algorithms","location":"New Orleans, LA, United States","end_date":"2018-01-10"},"publication_identifier":{"eisbn":["978-161197503-1"]},"author":[{"last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"first_name":"Deeparnab","full_name":"Chakrabarty, Deeparnab","last_name":"Chakrabarty"},{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Nanongkai","full_name":"Nanongkai, Danupon","first_name":"Danupon"}],"scopus_import":"1","year":"2018","extern":"1","external_id":{"arxiv":["1711.04355"]},"main_file_link":[{"url":"https://arxiv.org/abs/1711.04355","open_access":"1"}],"day":"01","oa":1,"status":"public","doi":"10.1137/1.9781611975031.1","date_published":"2018-01-01T00:00:00Z","quality_controlled":"1","arxiv":1,"month":"01","publication":"29th Annual ACM-SIAM Symposium on Discrete Algorithms","oa_version":"Preprint","citation":{"ama":"Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. Dynamic algorithms for graph coloring. In: <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2018:1-20. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.1\">10.1137/1.9781611975031.1</a>","mla":"Bhattacharya, Sayan, et al. “Dynamic Algorithms for Graph Coloring.” <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2018, pp. 1–20, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.1\">10.1137/1.9781611975031.1</a>.","apa":"Bhattacharya, S., Chakrabarty, D., Henzinger, M. H., &#38; Nanongkai, D. (2018). Dynamic algorithms for graph coloring. In <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1–20). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611975031.1\">https://doi.org/10.1137/1.9781611975031.1</a>","ieee":"S. Bhattacharya, D. Chakrabarty, M. H. Henzinger, and D. Nanongkai, “Dynamic algorithms for graph coloring,” in <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2018, pp. 1–20.","short":"S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, D. Nanongkai, in:, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2018, pp. 1–20.","ista":"Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika H Henzinger, and Danupon Nanongkai. “Dynamic Algorithms for Graph Coloring.” In <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1–20. Society for Industrial and Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.1\">https://doi.org/10.1137/1.9781611975031.1</a>."},"date_created":"2022-08-16T12:07:14Z","type":"conference"},{"scopus_import":"1","year":"2018","language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["978-1-61197-505-5"]},"author":[{"full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Noe, Alexander","last_name":"Noe","first_name":"Alexander"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"},{"full_name":"Strash, Darren","last_name":"Strash","first_name":"Darren"}],"conference":{"end_date":"2018-01-08","location":"New Orleans, LA, United States","name":"ALENEX: Symposium on Algorithm Engineering and Experiments","start_date":"2018-01-07"},"article_processing_charge":"No","date_updated":"2023-02-17T14:03:39Z","abstract":[{"lang":"eng","text":"The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Society for Industrial and Applied Mathematics","_id":"11882","publication_status":"published","page":"48-61","title":"Practical minimum cut algorithms","type":"conference","publication":"20th Workshop on Algorithm Engineering and Experiments","oa_version":"Preprint","citation":{"apa":"Henzinger, M. H., Noe, A., Schulz, C., &#38; Strash, D. (2018). Practical minimum cut algorithms. In <i>20th Workshop on Algorithm Engineering and Experiments</i> (pp. 48–61). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611975055.5\">https://doi.org/10.1137/1.9781611975055.5</a>","mla":"Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” <i>20th Workshop on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2018, pp. 48–61, doi:<a href=\"https://doi.org/10.1137/1.9781611975055.5\">10.1137/1.9781611975055.5</a>.","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. In: <i>20th Workshop on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2018:48-61. doi:<a href=\"https://doi.org/10.1137/1.9781611975055.5\">10.1137/1.9781611975055.5</a>","chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” In <i>20th Workshop on Algorithm Engineering and Experiments</i>, 48–61. Society for Industrial and Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/1.9781611975055.5\">https://doi.org/10.1137/1.9781611975055.5</a>.","ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” in <i>20th Workshop on Algorithm Engineering and Experiments</i>, New Orleans, LA, United States, 2018, pp. 48–61.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 20th Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2018, pp. 48–61."},"date_created":"2022-08-17T07:04:57Z","arxiv":1,"month":"01","quality_controlled":"1","doi":"10.1137/1.9781611975055.5","date_published":"2018-01-01T00:00:00Z","status":"public","external_id":{"arxiv":["1708.06127"]},"extern":"1","day":"01","main_file_link":[{"url":"https://arxiv.org/abs/1708.06127","open_access":"1"}],"oa":1},{"issue":"3","scopus_import":"1","year":"2018","volume":47,"abstract":[{"text":"We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464].","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_updated":"2023-02-21T16:31:30Z","author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Italiano","full_name":"Italiano, Giuseppe F.","first_name":"Giuseppe F."}],"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"language":[{"iso":"eng"}],"publication_status":"published","_id":"11890","publisher":"Society for Industrial & Applied Mathematics","article_type":"original","page":"859-887","title":"Deterministic fully dynamic data structures for vertex cover and matching","oa_version":"Preprint","citation":{"chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/140998925\">https://doi.org/10.1137/140998925</a>.","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887.","short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.","ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” <i>SIAM Journal on Computing</i>, vol. 47, no. 3. Society for Industrial &#38; Applied Mathematics, pp. 859–887, 2018.","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>SIAM Journal on Computing</i>, vol. 47, no. 3, Society for Industrial &#38; Applied Mathematics, 2018, pp. 859–87, doi:<a href=\"https://doi.org/10.1137/140998925\">10.1137/140998925</a>.","apa":"Bhattacharya, S., Henzinger, M. H., &#38; Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/140998925\">https://doi.org/10.1137/140998925</a>","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. <i>SIAM Journal on Computing</i>. 2018;47(3):859-887. doi:<a href=\"https://doi.org/10.1137/140998925\">10.1137/140998925</a>"},"date_created":"2022-08-17T08:21:23Z","publication":"SIAM Journal on Computing","type":"journal_article","quality_controlled":"1","month":"05","arxiv":1,"related_material":{"record":[{"id":"11875","relation":"earlier_version","status":"public"}]},"status":"public","doi":"10.1137/140998925","date_published":"2018-05-01T00:00:00Z","intvolume":"        47","oa":1,"extern":"1","external_id":{"arxiv":["1412.1318"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.1318"}],"day":"01"},{"status":"public","article_number":"3","doi":"10.4230/LIPICS.SEA.2018.3","date_published":"2018-07-01T00:00:00Z","intvolume":"       103","oa":1,"external_id":{"arxiv":["1802.07034"]},"extern":"1","day":"01","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.SEA.2018.3"}],"oa_version":"Published Version","citation":{"ama":"Biedermann S, Henzinger MH, Schulz C, Schuster B. Memetic graph clustering. In: <i>17th International Symposium on Experimental Algorithms</i>. Vol 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">10.4230/LIPICS.SEA.2018.3</a>","mla":"Biedermann, Sonja, et al. “Memetic Graph Clustering.” <i>17th International Symposium on Experimental Algorithms</i>, vol. 103, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">10.4230/LIPICS.SEA.2018.3</a>.","apa":"Biedermann, S., Henzinger, M. H., Schulz, C., &#38; Schuster, B. (2018). Memetic graph clustering. In <i>17th International Symposium on Experimental Algorithms</i> (Vol. 103). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">https://doi.org/10.4230/LIPICS.SEA.2018.3</a>","ieee":"S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Memetic graph clustering,” in <i>17th International Symposium on Experimental Algorithms</i>, L’Aquila, Italy, 2018, vol. 103.","short":"S. Biedermann, M.H. Henzinger, C. Schulz, B. Schuster, in:, 17th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ista":"Biedermann S, Henzinger MH, Schulz C, Schuster B. 2018. Memetic graph clustering. 17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 103, 3.","chicago":"Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster. “Memetic Graph Clustering.” In <i>17th International Symposium on Experimental Algorithms</i>, Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">https://doi.org/10.4230/LIPICS.SEA.2018.3</a>."},"date_created":"2022-08-18T06:49:40Z","publication":"17th International Symposium on Experimental Algorithms","type":"conference","quality_controlled":"1","month":"07","arxiv":1,"publication_status":"published","_id":"11911","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"title":"Memetic graph clustering","scopus_import":"1","year":"2018","volume":103,"abstract":[{"text":"It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation challenge under consideration using a small amount of time.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_updated":"2023-02-16T11:45:14Z","conference":{"start_date":"2018-07-27","name":"SEA: Symposium on Experimental Algorithms","location":"L'Aquila, Italy","end_date":"2018-07-29"},"author":[{"first_name":"Sonja","full_name":"Biedermann, Sonja","last_name":"Biedermann"},{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"},{"last_name":"Schuster","full_name":"Schuster, Bernhard","first_name":"Bernhard"}],"publication_identifier":{"isbn":["9783959770705"],"issn":["1868-8969"]},"language":[{"iso":"eng"}]},{"citation":{"ieee":"K. Nakashima, T. Auzinger, E. Iarussi, R. Zhang, T. Igarashi, and B. Bickel, “CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid molds,” <i>ACM Transaction on Graphics</i>, vol. 37, no. 4. ACM, 2018.","short":"K. Nakashima, T. Auzinger, E. Iarussi, R. Zhang, T. Igarashi, B. Bickel, ACM Transaction on Graphics 37 (2018).","chicago":"Nakashima, Kazutaka, Thomas Auzinger, Emmanuel Iarussi, Ran Zhang, Takeo Igarashi, and Bernd Bickel. “CoreCavity: Interactive Shell Decomposition for Fabrication with Two-Piece Rigid Molds.” <i>ACM Transaction on Graphics</i>. ACM, 2018. <a href=\"https://doi.org/10.1145/3197517.3201341\">https://doi.org/10.1145/3197517.3201341</a>.","ista":"Nakashima K, Auzinger T, Iarussi E, Zhang R, Igarashi T, Bickel B. 2018. CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid molds. ACM Transaction on Graphics. 37(4), 135.","ama":"Nakashima K, Auzinger T, Iarussi E, Zhang R, Igarashi T, Bickel B. CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid molds. <i>ACM Transaction on Graphics</i>. 2018;37(4). doi:<a href=\"https://doi.org/10.1145/3197517.3201341\">10.1145/3197517.3201341</a>","mla":"Nakashima, Kazutaka, et al. “CoreCavity: Interactive Shell Decomposition for Fabrication with Two-Piece Rigid Molds.” <i>ACM Transaction on Graphics</i>, vol. 37, no. 4, 135, ACM, 2018, doi:<a href=\"https://doi.org/10.1145/3197517.3201341\">10.1145/3197517.3201341</a>.","apa":"Nakashima, K., Auzinger, T., Iarussi, E., Zhang, R., Igarashi, T., &#38; Bickel, B. (2018). CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid molds. <i>ACM Transaction on Graphics</i>. ACM. <a href=\"https://doi.org/10.1145/3197517.3201341\">https://doi.org/10.1145/3197517.3201341</a>"},"oa_version":"Submitted Version","date_created":"2018-12-11T11:44:09Z","publication":"ACM Transaction on Graphics","type":"journal_article","quality_controlled":"1","pubrep_id":"1037","month":"08","related_material":{"link":[{"url":"https://ist.ac.at/en/news/interactive-software-tool-makes-complex-mold-design-simple/","relation":"press_release","description":"News on IST Homepage"}]},"status":"public","isi":1,"article_number":"135","doi":"10.1145/3197517.3201341","date_published":"2018-08-04T00:00:00Z","intvolume":"        37","oa":1,"external_id":{"isi":["000448185000096"]},"day":"04","scopus_import":"1","issue":"4","year":"2018","has_accepted_license":"1","volume":37,"abstract":[{"text":"Molding is a popular mass production method, in which the initial expenses for the mold are offset by the low per-unit production cost. However, the physical fabrication constraints of the molding technique commonly restrict the shape of moldable objects. For a complex shape, a decomposition of the object into moldable parts is a common strategy to address these constraints, with plastic model kits being a popular and illustrative example. However, conducting such a decomposition requires considerable expertise, and it depends on the technical aspects of the fabrication technique, as well as aesthetic considerations. We present an interactive technique to create such decompositions for two-piece molding, in which each part of the object is cast between two rigid mold pieces. Given the surface description of an object, we decompose its thin-shell equivalent into moldable parts by first performing a coarse decomposition and then utilizing an active contour model for the boundaries between individual parts. Formulated as an optimization problem, the movement of the contours is guided by an energy reflecting fabrication constraints to ensure the moldability of each part. Simultaneously, the user is provided with editing capabilities to enforce aesthetic guidelines. Our interactive interface provides control of the contour positions by allowing, for example, the alignment of part boundaries with object features. Our technique enables a novel workflow, as it empowers novice users to explore the design space, and it generates fabrication-ready two-piece molds that can be used either for casting or industrial injection molding of free-form objects.","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","file":[{"content_type":"application/pdf","access_level":"open_access","creator":"system","file_id":"5360","relation":"main_file","file_size":104225664,"date_created":"2018-12-12T10:18:38Z","file_name":"IST-2018-1037-v1+1_CoreCavity-AuthorVersion.pdf","date_updated":"2020-07-14T12:44:38Z","checksum":"6a5368bc86c4e1a9fcfe588fd1f14ee8"},{"date_updated":"2020-07-14T12:44:38Z","file_name":"IST-2018-1037-v1+2_CoreCavity-Supplemental.zip","checksum":"3861e693ba47c51f3ec7b7867d573a61","creator":"system","access_level":"open_access","content_type":"application/zip","relation":"main_file","file_id":"5361","date_created":"2018-12-12T10:18:39Z","file_size":377743553},{"date_created":"2018-12-12T10:18:41Z","file_size":162634396,"relation":"main_file","file_id":"5362","creator":"system","access_level":"open_access","content_type":"video/vnd.objectvideo","checksum":"490040c685ed869536e2a18f5a906b94","date_updated":"2020-07-14T12:44:38Z","file_name":"IST-2018-1037-v1+3_CoreCavity-Video.mp4"},{"checksum":"be7fc8b229adda727419b6504b3b9352","date_updated":"2020-07-14T12:44:38Z","file_name":"IST-2018-1037-v1+4_CoreCavity-RepresentativeImage.jpg","date_created":"2018-12-12T10:18:42Z","file_size":527972,"relation":"main_file","file_id":"5363","creator":"system","content_type":"image/jpeg","access_level":"open_access"}],"date_updated":"2023-09-11T12:48:09Z","author":[{"first_name":"Kazutaka","last_name":"Nakashima","full_name":"Nakashima, Kazutaka"},{"first_name":"Thomas","id":"4718F954-F248-11E8-B48F-1D18A9856A87","full_name":"Auzinger, Thomas","last_name":"Auzinger","orcid":"0000-0002-1546-3265"},{"first_name":"Emmanuel","id":"33F19F16-F248-11E8-B48F-1D18A9856A87","full_name":"Iarussi, Emmanuel","last_name":"Iarussi"},{"orcid":"0000-0002-3808-281X","id":"4DDBCEB0-F248-11E8-B48F-1D18A9856A87","last_name":"Zhang","full_name":"Zhang, Ran","first_name":"Ran"},{"first_name":"Takeo","full_name":"Igarashi, Takeo","last_name":"Igarashi"},{"last_name":"Bickel","id":"49876194-F248-11E8-B48F-1D18A9856A87","full_name":"Bickel, Bernd","first_name":"Bernd","orcid":"0000-0001-6511-9385"}],"language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:44:38Z","publication_status":"published","ddc":["004","516","670"],"ec_funded":1,"_id":"12","publisher":"ACM","publist_id":"8044","department":[{"_id":"BeBi"}],"title":"CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid molds","project":[{"_id":"24F9549A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling","grant_number":"715767"},{"name":"Distributed 3D Object Design","call_identifier":"H2020","_id":"2508E324-B435-11E9-9278-68D0E5697425","grant_number":"642841"}]},{"status":"public","intvolume":"        50","date_published":"2017-12-18T00:00:00Z","doi":"10.1038/s41588-017-0008-5","keyword":["Genetics"],"oa":1,"main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7611288/","open_access":"1"}],"day":"18","external_id":{"pmid":["29255257"]},"date_created":"2023-01-16T09:18:05Z","oa_version":"None","citation":{"chicago":"Walker, James, Hongbo Gao, Jingyi Zhang, Billy Aldridge, Martin Vickers, James D. Higgins, and Xiaoqi Feng. “Sexual-Lineage-Specific DNA Methylation Regulates Meiosis in Arabidopsis.” <i>Nature Genetics</i>. Nature Research, 2017. <a href=\"https://doi.org/10.1038/s41588-017-0008-5\">https://doi.org/10.1038/s41588-017-0008-5</a>.","ista":"Walker J, Gao H, Zhang J, Aldridge B, Vickers M, Higgins JD, Feng X. 2017. Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis. Nature Genetics. 50(1), 130–137.","short":"J. Walker, H. Gao, J. Zhang, B. Aldridge, M. Vickers, J.D. Higgins, X. Feng, Nature Genetics 50 (2017) 130–137.","ieee":"J. Walker <i>et al.</i>, “Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis,” <i>Nature Genetics</i>, vol. 50, no. 1. Nature Research, pp. 130–137, 2017.","mla":"Walker, James, et al. “Sexual-Lineage-Specific DNA Methylation Regulates Meiosis in Arabidopsis.” <i>Nature Genetics</i>, vol. 50, no. 1, Nature Research, 2017, pp. 130–37, doi:<a href=\"https://doi.org/10.1038/s41588-017-0008-5\">10.1038/s41588-017-0008-5</a>.","apa":"Walker, J., Gao, H., Zhang, J., Aldridge, B., Vickers, M., Higgins, J. D., &#38; Feng, X. (2017). Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis. <i>Nature Genetics</i>. Nature Research. <a href=\"https://doi.org/10.1038/s41588-017-0008-5\">https://doi.org/10.1038/s41588-017-0008-5</a>","ama":"Walker J, Gao H, Zhang J, et al. Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis. <i>Nature Genetics</i>. 2017;50(1):130-137. doi:<a href=\"https://doi.org/10.1038/s41588-017-0008-5\">10.1038/s41588-017-0008-5</a>"},"publication":"Nature Genetics","type":"journal_article","acknowledgement":"We thank Daniel Zilberman for intellectual contributions to this work and assistance with manuscript preparation. We also thank Caroline Dean, Kirsten Bomblies, Vinod Kumar, Siobhan Brady and Sophien Kamoun for comments on the manuscript, Hugh Dickinson and Josephine Hellberg for developing the meiocyte isolation method, Giles Oldroyd for the pGWB13-Bar vector, Elisa Fiume for the pMDC107-NTF vector, Matthew Hartley, Matthew Couchman and Tjelvar Sten Gunnar Olsson for bioinformatics support, and the John Innes Centre Bioimaging Facility (Elaine Barclay and Grant Calder) for their assistance with microscopy. This work was funded by a Biotechnology and Biological Sciences Research Council (BBSRC) David Phillips Fellowship (BBL0250431) to X.F., a BBSRC grant (BBM01973X1) to J.H., and a Sainsbury PhD Studentship to J.W.","quality_controlled":"1","month":"12","publication_status":"published","_id":"12193","article_type":"original","publisher":"Nature Research","department":[{"_id":"XiFe"}],"page":"130-137","title":"Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis","year":"2017","issue":"1","scopus_import":"1","volume":50,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"DNA methylation regulates eukaryotic gene expression and is extensively reprogrammed during animal development. However, whether developmental methylation reprogramming during the sporophytic life cycle of flowering plants regulates genes is presently unknown. Here we report a distinctive gene-targeted RNA-directed DNA methylation (RdDM) activity in the Arabidopsis thaliana male sexual lineage that regulates gene expression in meiocytes. Loss of sexual-lineage-specific RdDM causes mis-splicing of the MPS1 gene (also known as PRD2), thereby disrupting meiosis. Our results establish a regulatory paradigm in which de novo methylation creates a cell-lineage-specific epigenetic signature that controls gene expression and contributes to cellular function in flowering plants."}],"date_updated":"2023-10-18T07:21:53Z","article_processing_charge":"No","author":[{"last_name":"Walker","full_name":"Walker, James","first_name":"James"},{"full_name":"Gao, Hongbo","last_name":"Gao","first_name":"Hongbo"},{"last_name":"Zhang","full_name":"Zhang, Jingyi","first_name":"Jingyi"},{"first_name":"Billy","last_name":"Aldridge","full_name":"Aldridge, Billy"},{"full_name":"Vickers, Martin","last_name":"Vickers","first_name":"Martin"},{"first_name":"James D.","full_name":"Higgins, James D.","last_name":"Higgins"},{"first_name":"Xiaoqi","full_name":"Feng, Xiaoqi","last_name":"Feng","id":"e0164712-22ee-11ed-b12a-d80fcdf35958","orcid":"0000-0002-4008-1234"}],"publication_identifier":{"eissn":["1546-1718"],"issn":["1061-4036"]},"language":[{"iso":"eng"}],"pmid":1},{"month":"01","pubrep_id":"738","acknowledgement":"This work was supported by grants of the Austrian Science Fund (FWF) P23585B09 to M.W. and F3506 to H.H.S. and the “Wiener Wissenschafts-, Forschungs- und Technologiefonds” (Vienna Science and Technology Fund; WWTF) CS15-033 to M.W.","quality_controlled":"1","type":"journal_article","citation":{"ama":"Sauerzopf U, Sacco R, Novarino G, et al. Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence. <i>European Journal of Neuroscience</i>. 2017;45(1):45-57. doi:<a href=\"https://doi.org/10.1111/ejn.13418\">10.1111/ejn.13418</a>","mla":"Sauerzopf, Ulrich, et al. “Are Reprogrammed Cells a Useful Tool for Studying Dopamine Dysfunction in Psychotic Disorders? A Review of the Current Evidence.” <i>European Journal of Neuroscience</i>, vol. 45, no. 1, Wiley-Blackwell, 2017, pp. 45–57, doi:<a href=\"https://doi.org/10.1111/ejn.13418\">10.1111/ejn.13418</a>.","apa":"Sauerzopf, U., Sacco, R., Novarino, G., Niello, M., Weidenauer, A., Praschak Rieder, N., … Willeit, M. (2017). Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence. <i>European Journal of Neuroscience</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/ejn.13418\">https://doi.org/10.1111/ejn.13418</a>","short":"U. Sauerzopf, R. Sacco, G. Novarino, M. Niello, A. Weidenauer, N. Praschak Rieder, H. Sitte, M. Willeit, European Journal of Neuroscience 45 (2017) 45–57.","ieee":"U. Sauerzopf <i>et al.</i>, “Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence,” <i>European Journal of Neuroscience</i>, vol. 45, no. 1. Wiley-Blackwell, pp. 45–57, 2017.","chicago":"Sauerzopf, Ulrich, Roberto Sacco, Gaia Novarino, Marco Niello, Ana Weidenauer, Nicole Praschak Rieder, Harald Sitte, and Matthaeus Willeit. “Are Reprogrammed Cells a Useful Tool for Studying Dopamine Dysfunction in Psychotic Disorders? A Review of the Current Evidence.” <i>European Journal of Neuroscience</i>. Wiley-Blackwell, 2017. <a href=\"https://doi.org/10.1111/ejn.13418\">https://doi.org/10.1111/ejn.13418</a>.","ista":"Sauerzopf U, Sacco R, Novarino G, Niello M, Weidenauer A, Praschak Rieder N, Sitte H, Willeit M. 2017. Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence. European Journal of Neuroscience. 45(1), 45–57."},"oa_version":"Published Version","date_created":"2018-12-11T11:50:50Z","publication":"European Journal of Neuroscience","oa":1,"external_id":{"isi":["000392487100005"],"pmid":["27690184"]},"day":"01","isi":1,"doi":"10.1111/ejn.13418","date_published":"2017-01-01T00:00:00Z","intvolume":"        45","status":"public","author":[{"full_name":"Sauerzopf, Ulrich","last_name":"Sauerzopf","first_name":"Ulrich"},{"id":"42C9F57E-F248-11E8-B48F-1D18A9856A87","full_name":"Sacco, Roberto","last_name":"Sacco","first_name":"Roberto"},{"orcid":"0000-0002-7673-7178","last_name":"Novarino","id":"3E57A680-F248-11E8-B48F-1D18A9856A87","full_name":"Novarino, Gaia","first_name":"Gaia"},{"last_name":"Niello","full_name":"Niello, Marco","first_name":"Marco"},{"full_name":"Weidenauer, Ana","last_name":"Weidenauer","first_name":"Ana"},{"last_name":"Praschak Rieder","full_name":"Praschak Rieder, Nicole","first_name":"Nicole"},{"last_name":"Sitte","full_name":"Sitte, Harald","first_name":"Harald"},{"last_name":"Willeit","full_name":"Willeit, Matthaeus","first_name":"Matthaeus"}],"pmid":1,"language":[{"iso":"eng"}],"abstract":[{"text":"Since 2006, reprogrammed cells have increasingly been used as a biomedical research technique in addition to neuro-psychiatric methods. These rapidly evolving techniques allow for the generation of neuronal sub-populations, and have sparked interest not only in monogenetic neuro-psychiatric diseases, but also in poly-genetic and poly-aetiological disorders such as schizophrenia (SCZ) and bipolar disorder (BPD). This review provides a summary of 19 publications on reprogrammed adult somatic cells derived from patients with SCZ, and five publications using this technique in patients with BPD. As both disorders are complex and heterogeneous, there is a plurality of hypotheses to be tested in vitro. In SCZ, data on alterations of dopaminergic transmission in vitro are sparse, despite the great explanatory power of the so-called DA hypothesis of SCZ. Some findings correspond to perturbations of cell energy metabolism, and observations in reprogrammed cells suggest neuro-developmental alterations. Some studies also report on the efficacy of medicinal compounds to revert alterations observed in cellular models. However, due to the paucity of replication studies, no comprehensive conclusions can be drawn from studies using reprogrammed cells at the present time. In the future, findings from cell culture methods need to be integrated with clinical, epidemiological, pharmacological and imaging data in order to generate a more comprehensive picture of SCZ and BPD.","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","date_updated":"2023-09-20T11:16:01Z","file":[{"checksum":"c572cf02be8fbb7020cfcfb892182e4c","date_updated":"2020-07-14T12:44:39Z","file_name":"IST-2017-738-v1+1_Sauerzopf_et_al-2017-European_Journal_of_Neuroscience.pdf","date_created":"2018-12-12T10:10:48Z","file_size":169145,"relation":"main_file","file_id":"4838","creator":"system","content_type":"application/pdf","access_level":"open_access"}],"has_accepted_license":"1","volume":45,"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"issue":"1","scopus_import":"1","year":"2017","page":"45 - 57","title":"Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence","department":[{"_id":"GaNo"}],"_id":"1228","publisher":"Wiley-Blackwell","publist_id":"6106","article_type":"review","ddc":["616"],"file_date_updated":"2020-07-14T12:44:39Z","publication_status":"published"},{"author":[{"orcid":"0000-0002-2299-3176","first_name":"Scott R","full_name":"Waitukaitis, Scott R","last_name":"Waitukaitis","id":"3A1FFC16-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Antal","last_name":"Zuiderwijk","full_name":"Zuiderwijk, Antal"},{"last_name":"Souslov","full_name":"Souslov, Anton","first_name":"Anton"},{"full_name":"Coulais, Corentin","last_name":"Coulais","first_name":"Corentin"},{"full_name":"Van Hecke, Martin","last_name":"Van Hecke","first_name":"Martin"}],"language":[{"iso":"eng"}],"abstract":[{"text":"The Leidenfrost effect occurs when an object near a hot surface vaporizes rapidly enough to lift itself up and hover. Although well understood for liquids and stiff sublimable solids, nothing is known about the effect with materials whose stiffness lies between these extremes. Here we introduce a new phenomenon that occurs with vaporizable soft solids - the elastic Leidenfrost effect. By dropping hydrogel spheres onto hot surfaces we find that, rather than hovering, they energetically bounce several times their diameter for minutes at a time. With high-speed video during a single impact, we uncover high-frequency microscopic gap dynamics at the sphere/substrate interface. We show how these otherwise-hidden agitations constitute work cycles that harvest mechanical energy from the vapour and sustain the bouncing. Our findings suggest a new strategy for injecting mechanical energy into a widely used class of soft materials, with potential relevance to fields such as active matter, soft robotics and microfluidics.","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:49:14Z","volume":13,"issue":"11","year":"2017","title":"Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing","page":"1095 - 1099","_id":"123","publisher":"Nature Publishing Group","publist_id":"7931","publication_status":"published","month":"07","arxiv":1,"acknowledgement":"A.S. acknowledges funding from the Delta Institute for Theoretical Physics and the hospitality of the IBS Center for Theoretical Physics of Complex Systems, Daejeon, South Korea. We acknowledge funding from the Netherlands Organisation for Scientific Research through grants VICI No. NWO-680-47-609 (M.v.H. and S.R.W.), VENI No. NWO-680-47-445 (C.C.) and VENI No. NWO-680-47-453 (S.R.W.).","quality_controlled":"1","type":"journal_article","oa_version":"Preprint","citation":{"ista":"Waitukaitis SR, Zuiderwijk A, Souslov A, Coulais C, Van Hecke M. 2017. Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing. Nature Physics. 13(11), 1095–1099.","chicago":"Waitukaitis, Scott R, Antal Zuiderwijk, Anton Souslov, Corentin Coulais, and Martin Van Hecke. “Coupling the Leidenfrost Effect and Elastic Deformations to Power Sustained Bouncing.” <i>Nature Physics</i>. Nature Publishing Group, 2017. <a href=\"https://doi.org/10.1038/nphys4194\">https://doi.org/10.1038/nphys4194</a>.","short":"S.R. Waitukaitis, A. Zuiderwijk, A. Souslov, C. Coulais, M. Van Hecke, Nature Physics 13 (2017) 1095–1099.","ieee":"S. R. Waitukaitis, A. Zuiderwijk, A. Souslov, C. Coulais, and M. Van Hecke, “Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing,” <i>Nature Physics</i>, vol. 13, no. 11. Nature Publishing Group, pp. 1095–1099, 2017.","mla":"Waitukaitis, Scott R., et al. “Coupling the Leidenfrost Effect and Elastic Deformations to Power Sustained Bouncing.” <i>Nature Physics</i>, vol. 13, no. 11, Nature Publishing Group, 2017, pp. 1095–99, doi:<a href=\"https://doi.org/10.1038/nphys4194\">10.1038/nphys4194</a>.","apa":"Waitukaitis, S. R., Zuiderwijk, A., Souslov, A., Coulais, C., &#38; Van Hecke, M. (2017). Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing. <i>Nature Physics</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nphys4194\">https://doi.org/10.1038/nphys4194</a>","ama":"Waitukaitis SR, Zuiderwijk A, Souslov A, Coulais C, Van Hecke M. Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing. <i>Nature Physics</i>. 2017;13(11):1095-1099. doi:<a href=\"https://doi.org/10.1038/nphys4194\">10.1038/nphys4194</a>"},"date_created":"2018-12-11T11:44:45Z","publication":"Nature Physics","oa":1,"extern":"1","external_id":{"arxiv":["1705.03530"]},"day":"24","main_file_link":[{"url":"https://arxiv.org/abs/1705.03530","open_access":"1"}],"date_published":"2017-07-24T00:00:00Z","doi":"10.1038/nphys4194","intvolume":"        13","status":"public"},{"intvolume":"     10328","date_published":"2017-05-24T00:00:00Z","doi":"10.1007/978-3-319-59250-3_8","status":"public","day":"24","main_file_link":[{"url":"https://arxiv.org/abs/1611.00198","open_access":"1"}],"external_id":{"arxiv":["1611.00198"]},"extern":"1","oa":1,"type":"conference","publication":"19th International Conference on Integer Programming and Combinatorial Optimization","date_created":"2023-02-20T07:52:31Z","citation":{"chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.” In <i>19th International Conference on Integer Programming and Combinatorial Optimization</i>, 10328:86–98. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/978-3-319-59250-3_8\">https://doi.org/10.1007/978-3-319-59250-3_8</a>.","ista":"Bhattacharya S, Chakrabarty D, Henzinger MH. 2017. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. 19th International Conference on Integer Programming and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 10328, 86–98.","short":"S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, in:, 19th International Conference on Integer Programming and Combinatorial Optimization, Springer Nature, 2017, pp. 86–98.","ieee":"S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time,” in <i>19th International Conference on Integer Programming and Combinatorial Optimization</i>, Waterloo, ON, Canada, 2017, vol. 10328, pp. 86–98.","apa":"Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. H. (2017). Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In <i>19th International Conference on Integer Programming and Combinatorial Optimization</i> (Vol. 10328, pp. 86–98). Waterloo, ON, Canada: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-59250-3_8\">https://doi.org/10.1007/978-3-319-59250-3_8</a>","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.” <i>19th International Conference on Integer Programming and Combinatorial Optimization</i>, vol. 10328, Springer Nature, 2017, pp. 86–98, doi:<a href=\"https://doi.org/10.1007/978-3-319-59250-3_8\">10.1007/978-3-319-59250-3_8</a>.","ama":"Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In: <i>19th International Conference on Integer Programming and Combinatorial Optimization</i>. Vol 10328. Springer Nature; 2017:86-98. doi:<a href=\"https://doi.org/10.1007/978-3-319-59250-3_8\">10.1007/978-3-319-59250-3_8</a>"},"oa_version":"Preprint","arxiv":1,"month":"05","quality_controlled":"1","publisher":"Springer Nature","_id":"12571","publication_status":"published","page":"86-98","title":"Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time","alternative_title":["LNCS"],"volume":10328,"year":"2017","scopus_import":"1","language":[{"iso":"eng"}],"author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab","first_name":"Deeparnab"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"}],"conference":{"start_date":"2017-06-26","location":"Waterloo, ON, Canada","name":"IPCO: Integer Programming and Combinatorial Optimization","end_date":"2017-06-28"},"publication_identifier":{"issn":["0302-9743","1611-3349"],"eisbn":["9783319592503"],"isbn":["9783319592497"]},"date_updated":"2023-02-20T07:57:24Z","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We consider the problems of maintaining approximate maximum matching and minimum vertex cover in a dynamic graph. Starting with the seminal work of Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011], Solomon [FOCS 2016] gave a randomized 2-approximation dynamic algorithm for this problem that has amortized update time of O(1) with high probability. We consider the natural open question of derandomizing this result. 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, Henzinger and Italiano [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)-approximation algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional matching problems, where every hyperedge has at most f vertices.","lang":"eng"}]},{"oa":1,"extern":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1017/jog.2017.65"}],"day":"01","keyword":["Earth-Surface Processes"],"doi":"10.1017/jog.2017.65","date_published":"2017-12-01T00:00:00Z","intvolume":"        63","status":"public","month":"12","quality_controlled":"1","type":"journal_article","citation":{"ieee":"T. E. SHAW, B. W. BROCK, Á. AYALA, N. RUTTER, and F. Pellicciotti, “Centreline and cross-glacier air temperature variability on an Alpine glacier: Assessing temperature distribution methods and their influence on melt model calculations,” <i>Journal of Glaciology</i>, vol. 63, no. 242. Cambridge University Press, pp. 973–988, 2017.","short":"T.E. SHAW, B.W. BROCK, Á. AYALA, N. RUTTER, F. Pellicciotti, Journal of Glaciology 63 (2017) 973–988.","ista":"SHAW TE, BROCK BW, AYALA Á, RUTTER N, Pellicciotti F. 2017. Centreline and cross-glacier air temperature variability on an Alpine glacier: Assessing temperature distribution methods and their influence on melt model calculations. Journal of Glaciology. 63(242), 973–988.","chicago":"SHAW, THOMAS E., BEN W. BROCK, ÁLVARO AYALA, NICK RUTTER, and Francesca Pellicciotti. “Centreline and Cross-Glacier Air Temperature Variability on an Alpine Glacier: Assessing Temperature Distribution Methods and Their Influence on Melt Model Calculations.” <i>Journal of Glaciology</i>. Cambridge University Press, 2017. <a href=\"https://doi.org/10.1017/jog.2017.65\">https://doi.org/10.1017/jog.2017.65</a>.","ama":"SHAW TE, BROCK BW, AYALA Á, RUTTER N, Pellicciotti F. Centreline and cross-glacier air temperature variability on an Alpine glacier: Assessing temperature distribution methods and their influence on melt model calculations. <i>Journal of Glaciology</i>. 2017;63(242):973-988. doi:<a href=\"https://doi.org/10.1017/jog.2017.65\">10.1017/jog.2017.65</a>","mla":"SHAW, THOMAS E., et al. “Centreline and Cross-Glacier Air Temperature Variability on an Alpine Glacier: Assessing Temperature Distribution Methods and Their Influence on Melt Model Calculations.” <i>Journal of Glaciology</i>, vol. 63, no. 242, Cambridge University Press, 2017, pp. 973–88, doi:<a href=\"https://doi.org/10.1017/jog.2017.65\">10.1017/jog.2017.65</a>.","apa":"SHAW, T. E., BROCK, B. W., AYALA, Á., RUTTER, N., &#38; Pellicciotti, F. (2017). Centreline and cross-glacier air temperature variability on an Alpine glacier: Assessing temperature distribution methods and their influence on melt model calculations. <i>Journal of Glaciology</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/jog.2017.65\">https://doi.org/10.1017/jog.2017.65</a>"},"oa_version":"Published Version","date_created":"2023-02-20T08:13:47Z","publication":"Journal of Glaciology","title":"Centreline and cross-glacier air temperature variability on an Alpine glacier: Assessing temperature distribution methods and their influence on melt model calculations","page":"973-988","_id":"12608","publisher":"Cambridge University Press","article_type":"original","publication_status":"published","author":[{"full_name":"SHAW, THOMAS E.","last_name":"SHAW","first_name":"THOMAS E."},{"full_name":"BROCK, BEN W.","last_name":"BROCK","first_name":"BEN W."},{"full_name":"AYALA, ÁLVARO","last_name":"AYALA","first_name":"ÁLVARO"},{"first_name":"NICK","full_name":"RUTTER, NICK","last_name":"RUTTER"},{"id":"b28f055a-81ea-11ed-b70c-a9fe7f7b0e70","last_name":"Pellicciotti","full_name":"Pellicciotti, Francesca","first_name":"Francesca"}],"publication_identifier":{"issn":["0022-1430"],"eissn":["1727-5652"]},"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"The spatio-temporal distribution of air temperature over mountain glaciers can demonstrate complex patterns, yet it is often represented simplistically using linear vertical temperature gradients (VTGs) extrapolated from off-glacier locations. We analyse a network of centreline and lateral air temperature observations at Tsanteleina Glacier, Italy, during summer 2015. On average, VTGs are steep (&lt;−0.0065 °C m<jats:sup>−1</jats:sup>), but they are shallow under warm ambient conditions when the correlation between air temperature and elevation becomes weaker. Published along-flowline temperature distribution methods explain centreline observations well, including warming on the lower glacier tongue, but cannot estimate lateral temperature variability. Application of temperature distribution methods improves simulation of melt rates (RMSE) in an energy-balance model by up to 36% compared to the environmental lapse rate extrapolated from an off-glacier station. However, results suggest that model parameters are not easily transferable to glaciers with a small fetch without recalibration. Such methods have potential to improve estimates of temperature across a glacier, but their parameter transferability should be further linked to the glacier and atmospheric characteristics. Furthermore, ‘cold spots’, which can be &gt;2°C cooler than expected for their elevation, whose occurrence is not predicted by the temperature distribution models, are identified at one-quarter of the measurement sites."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_updated":"2023-02-28T11:30:34Z","volume":63,"scopus_import":"1","issue":"242","year":"2017"},{"oa_version":"Published Version","citation":{"ama":"AYALA A, Pellicciotti F, PELEG N, BURLANDO P. Melt and surface sublimation across a glacier in a dry environment: distributed energy-balance modelling of Juncal Norte Glacier, Chile. <i>Journal of Glaciology</i>. 2017;63(241):803-822. doi:<a href=\"https://doi.org/10.1017/jog.2017.46\">10.1017/jog.2017.46</a>","apa":"AYALA, A., Pellicciotti, F., PELEG, N., &#38; BURLANDO, P. (2017). Melt and surface sublimation across a glacier in a dry environment: distributed energy-balance modelling of Juncal Norte Glacier, Chile. <i>Journal of Glaciology</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/jog.2017.46\">https://doi.org/10.1017/jog.2017.46</a>","mla":"AYALA, A., et al. “Melt and Surface Sublimation across a Glacier in a Dry Environment: Distributed Energy-Balance Modelling of Juncal Norte Glacier, Chile.” <i>Journal of Glaciology</i>, vol. 63, no. 241, Cambridge University Press, 2017, pp. 803–22, doi:<a href=\"https://doi.org/10.1017/jog.2017.46\">10.1017/jog.2017.46</a>.","short":"A. AYALA, F. Pellicciotti, N. PELEG, P. BURLANDO, Journal of Glaciology 63 (2017) 803–822.","ieee":"A. AYALA, F. Pellicciotti, N. PELEG, and P. BURLANDO, “Melt and surface sublimation across a glacier in a dry environment: distributed energy-balance modelling of Juncal Norte Glacier, Chile,” <i>Journal of Glaciology</i>, vol. 63, no. 241. Cambridge University Press, pp. 803–822, 2017.","ista":"AYALA A, Pellicciotti F, PELEG N, BURLANDO P. 2017. Melt and surface sublimation across a glacier in a dry environment: distributed energy-balance modelling of Juncal Norte Glacier, Chile. Journal of Glaciology. 63(241), 803–822.","chicago":"AYALA, A., Francesca Pellicciotti, N. PELEG, and P. BURLANDO. “Melt and Surface Sublimation across a Glacier in a Dry Environment: Distributed Energy-Balance Modelling of Juncal Norte Glacier, Chile.” <i>Journal of Glaciology</i>. Cambridge University Press, 2017. <a href=\"https://doi.org/10.1017/jog.2017.46\">https://doi.org/10.1017/jog.2017.46</a>."},"date_created":"2023-02-20T08:13:53Z","publication":"Journal of Glaciology","type":"journal_article","quality_controlled":"1","month":"10","status":"public","date_published":"2017-10-01T00:00:00Z","doi":"10.1017/jog.2017.46","intvolume":"        63","keyword":["Earth-Surface Processes"],"oa":1,"extern":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1017/jog.2017.46"}],"day":"01","scopus_import":"1","issue":"241","year":"2017","volume":63,"abstract":[{"lang":"eng","text":"Previous estimates of melt and surface sublimation on glaciers of the subtropical semiarid Andes (29–34°S) have been obtained at few specific locations, but it is not clear how ablation components vary across the entire extent of a glacier in this dry environment. Here, we simulate the distributed energy and mass balance of Juncal Norte Glacier (33°S) during a 2-month summer period. Forcing fields of near-surface air temperature and wind speed are generated using two methods accounting for the main physical processes that shape their spatial variations. Simulated meteorological variables and ablation agree well with observations on the glacier tongue and reveal complex patterns of energy and mass fluxes. Ablation decreases from 70 mm w.e. d<jats:sup>−1</jats:sup> at the low-albedo glacier terminus (~3000 m), where almost 100% of total ablation corresponds to melt, to &lt;5 mm w.e. d<jats:sup>−1</jats:sup> at wind-exposed, strong-radiated sites above 5500 m, where surface sublimation represents &gt;75% of total ablation. Our simulations provide the first glacier-scale estimates of ablation components on a glacier in the study region and better reproduce the observed and expected spatial variations of melt and surface sublimation, in comparison with more simple assumptions, such as linear gradients and uniform wind speeds."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_updated":"2023-02-28T11:28:19Z","author":[{"last_name":"AYALA","full_name":"AYALA, A.","first_name":"A."},{"first_name":"Francesca","last_name":"Pellicciotti","full_name":"Pellicciotti, Francesca","id":"b28f055a-81ea-11ed-b70c-a9fe7f7b0e70"},{"first_name":"N.","full_name":"PELEG, N.","last_name":"PELEG"},{"first_name":"P.","last_name":"BURLANDO","full_name":"BURLANDO, P."}],"publication_identifier":{"eissn":["1727-5652"],"issn":["0022-1430"]},"language":[{"iso":"eng"}],"publication_status":"published","_id":"12609","publisher":"Cambridge University Press","article_type":"original","title":"Melt and surface sublimation across a glacier in a dry environment: distributed energy-balance modelling of Juncal Norte Glacier, Chile","page":"803-822"},{"quality_controlled":"1","month":"09","publication":"Frontiers in Earth Science","date_created":"2023-02-20T08:14:04Z","citation":{"ama":"Miles ES, Steiner J, Willis I, et al. Pond dynamics and supraglacial-englacial connectivity on debris-covered Lirung Glacier, Nepal. <i>Frontiers in Earth Science</i>. 2017;5. doi:<a href=\"https://doi.org/10.3389/feart.2017.00069\">10.3389/feart.2017.00069</a>","mla":"Miles, Evan S., et al. “Pond Dynamics and Supraglacial-Englacial Connectivity on Debris-Covered Lirung Glacier, Nepal.” <i>Frontiers in Earth Science</i>, vol. 5, 69, Frontiers Media, 2017, doi:<a href=\"https://doi.org/10.3389/feart.2017.00069\">10.3389/feart.2017.00069</a>.","apa":"Miles, E. S., Steiner, J., Willis, I., Buri, P., Immerzeel, W. W., Chesnokova, A., &#38; Pellicciotti, F. (2017). Pond dynamics and supraglacial-englacial connectivity on debris-covered Lirung Glacier, Nepal. <i>Frontiers in Earth Science</i>. Frontiers Media. <a href=\"https://doi.org/10.3389/feart.2017.00069\">https://doi.org/10.3389/feart.2017.00069</a>","ieee":"E. S. Miles <i>et al.</i>, “Pond dynamics and supraglacial-englacial connectivity on debris-covered Lirung Glacier, Nepal,” <i>Frontiers in Earth Science</i>, vol. 5. Frontiers Media, 2017.","short":"E.S. Miles, J. Steiner, I. Willis, P. Buri, W.W. Immerzeel, A. Chesnokova, F. Pellicciotti, Frontiers in Earth Science 5 (2017).","ista":"Miles ES, Steiner J, Willis I, Buri P, Immerzeel WW, Chesnokova A, Pellicciotti F. 2017. Pond dynamics and supraglacial-englacial connectivity on debris-covered Lirung Glacier, Nepal. Frontiers in Earth Science. 5, 69.","chicago":"Miles, Evan S., Jakob Steiner, Ian Willis, Pascal Buri, Walter W. Immerzeel, Anna Chesnokova, and Francesca Pellicciotti. “Pond Dynamics and Supraglacial-Englacial Connectivity on Debris-Covered Lirung Glacier, Nepal.” <i>Frontiers in Earth Science</i>. Frontiers Media, 2017. <a href=\"https://doi.org/10.3389/feart.2017.00069\">https://doi.org/10.3389/feart.2017.00069</a>."},"oa_version":"Published Version","type":"journal_article","keyword":["General Earth and Planetary Sciences"],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.3389/feart.2017.00069"}],"day":"21","extern":"1","oa":1,"status":"public","intvolume":"         5","date_published":"2017-09-21T00:00:00Z","doi":"10.3389/feart.2017.00069","article_number":"69","date_updated":"2023-02-28T11:13:23Z","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"The hydrological systems of heavily-downwasted debris-covered glaciers differ from those of clean-ice glaciers due to the hummocky surface and debris mantle of such glaciers, leading to a relatively limited understanding of drainage pathways. Supraglacial ponds represent sinks within the discontinuous supraglacial drainage system, and occasionally drain englacially. To assess pond dynamics, we made pond water level measurements on Lirung Glacier, Nepal, during May and October of 2013 and 2014. Simultaneously, aerial, satellite, and terrestrial orthoimages and digital elevation models were obtained, providing snapshots of the ponds and their surroundings. We performed a DEM-based analysis of the glacier's closed surface catchments to identify surface drainage pathways and englacial drainage points, and compared this to field observations of surface and near-surface water flow. The total ponded area was higher in the pre-monsoon than post-monsoon, with individual ponds filling and draining seasonally associated with the surface exposure of englacial conduit segments. We recorded four pond drainage events, all of which occurred gradually (duration of weeks), observed diurnal fluctuations indicative of varying water supply and outflow discharge, and we documented instances of interaction between distant ponds. The DEM drainage analysis identified numerous sinks >3 m in depth across the glacier surface, few of which exhibited ponds (23%), while the field survey highlighted instances of surface water only explicable via englacial routes. Taken together, our observations provide evidence for widespread supraglacial-englacial connectivity of meltwater drainage paths. Results suggest that successive englacial conduit collapse events, themselves likely driven by supraglacial pond drainage, cause the glacier surface drainage system to evolve into a configuration following relict englacial conduit systems. Within this system, ponds form in depressions of reduced drainage efficiency and link the supraglacial and englacial drainage networks."}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2296-6463"]},"author":[{"full_name":"Miles, Evan S.","last_name":"Miles","first_name":"Evan S."},{"first_name":"Jakob","full_name":"Steiner, Jakob","last_name":"Steiner"},{"last_name":"Willis","full_name":"Willis, Ian","first_name":"Ian"},{"first_name":"Pascal","full_name":"Buri, Pascal","last_name":"Buri"},{"first_name":"Walter W.","full_name":"Immerzeel, Walter W.","last_name":"Immerzeel"},{"last_name":"Chesnokova","full_name":"Chesnokova, Anna","first_name":"Anna"},{"full_name":"Pellicciotti, Francesca","id":"b28f055a-81ea-11ed-b70c-a9fe7f7b0e70","last_name":"Pellicciotti","first_name":"Francesca"}],"year":"2017","scopus_import":"1","volume":5,"title":"Pond dynamics and supraglacial-englacial connectivity on debris-covered Lirung Glacier, Nepal","publication_status":"published","article_type":"original","publisher":"Frontiers Media","_id":"12610"},{"quality_controlled":"1","month":"02","publication":"Journal of Glaciology","oa_version":"Published Version","citation":{"mla":"MILES, EVAN S., et al. “Spatial, Seasonal and Interannual Variability of Supraglacial Ponds in the Langtang Valley of Nepal, 1999–2013.” <i>Journal of Glaciology</i>, vol. 63, no. 237, Cambridge University Press, 2017, pp. 88–105, doi:<a href=\"https://doi.org/10.1017/jog.2016.120\">10.1017/jog.2016.120</a>.","apa":"MILES, E. S., WILLIS, I. C., ARNOLD, N. S., STEINER, J., &#38; Pellicciotti, F. (2017). Spatial, seasonal and interannual variability of supraglacial ponds in the Langtang Valley of Nepal, 1999–2013. <i>Journal of Glaciology</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/jog.2016.120\">https://doi.org/10.1017/jog.2016.120</a>","ama":"MILES ES, WILLIS IC, ARNOLD NS, STEINER J, Pellicciotti F. Spatial, seasonal and interannual variability of supraglacial ponds in the Langtang Valley of Nepal, 1999–2013. <i>Journal of Glaciology</i>. 2017;63(237):88-105. doi:<a href=\"https://doi.org/10.1017/jog.2016.120\">10.1017/jog.2016.120</a>","ista":"MILES ES, WILLIS IC, ARNOLD NS, STEINER J, Pellicciotti F. 2017. Spatial, seasonal and interannual variability of supraglacial ponds in the Langtang Valley of Nepal, 1999–2013. Journal of Glaciology. 63(237), 88–105.","chicago":"MILES, EVAN S., IAN C. WILLIS, NEIL S. ARNOLD, JAKOB STEINER, and Francesca Pellicciotti. “Spatial, Seasonal and Interannual Variability of Supraglacial Ponds in the Langtang Valley of Nepal, 1999–2013.” <i>Journal of Glaciology</i>. Cambridge University Press, 2017. <a href=\"https://doi.org/10.1017/jog.2016.120\">https://doi.org/10.1017/jog.2016.120</a>.","short":"E.S. MILES, I.C. WILLIS, N.S. ARNOLD, J. STEINER, F. Pellicciotti, Journal of Glaciology 63 (2017) 88–105.","ieee":"E. S. MILES, I. C. WILLIS, N. S. ARNOLD, J. STEINER, and F. Pellicciotti, “Spatial, seasonal and interannual variability of supraglacial ponds in the Langtang Valley of Nepal, 1999–2013,” <i>Journal of Glaciology</i>, vol. 63, no. 237. Cambridge University Press, pp. 88–105, 2017."},"date_created":"2023-02-20T08:14:16Z","type":"journal_article","keyword":["Earth-Surface Processes"],"extern":"1","day":"01","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1017/jog.2016.120"}],"oa":1,"status":"public","date_published":"2017-02-01T00:00:00Z","doi":"10.1017/jog.2016.120","intvolume":"        63","article_processing_charge":"No","date_updated":"2023-02-24T11:38:31Z","abstract":[{"lang":"eng","text":"Supraglacial ponds play a key role in absorbing atmospheric energy and directing it to the ice of debris-covered glaciers, but the spatial and temporal distribution of these features is not well documented. We analyse 172 Landsat TM/ETM+ scenes for the period 1999–2013 to identify thawed supraglacial ponds for the debris-covered tongues of five glaciers in the Langtang Valley of Nepal. We apply an advanced atmospheric correction routine (Landcor/6S) and use band ratio and image morphological techniques to identify ponds and validate our results with 2.5 m Cartosat-1 observations. We then characterize the spatial, seasonal and interannual patterns of ponds. We find high variability in pond incidence between glaciers (May–October means of 0.08–1.69% of debris area), with ponds most frequent in zones of low surface gradient and velocity. The ponds show pronounced seasonality, appearing in the pre-monsoon as snow melts, peaking at the monsoon onset at 2% of debris-covered area, then declining in the post-monsoon as ponds drain or freeze. Ponds are highly recurrent and persistent, with 40.5% of pond locations occurring for multiple years. Rather than a trend in pond cover over the study period, we find high interannual variability for each glacier after controlling for seasonality."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1727-5652"],"issn":["0022-1430"]},"author":[{"full_name":"MILES, EVAN S.","last_name":"MILES","first_name":"EVAN S."},{"last_name":"WILLIS","full_name":"WILLIS, IAN C.","first_name":"IAN C."},{"first_name":"NEIL S.","last_name":"ARNOLD","full_name":"ARNOLD, NEIL S."},{"first_name":"JAKOB","full_name":"STEINER, JAKOB","last_name":"STEINER"},{"first_name":"Francesca","full_name":"Pellicciotti, Francesca","id":"b28f055a-81ea-11ed-b70c-a9fe7f7b0e70","last_name":"Pellicciotti"}],"issue":"237","scopus_import":"1","year":"2017","volume":63,"title":"Spatial, seasonal and interannual variability of supraglacial ponds in the Langtang Valley of Nepal, 1999–2013","page":"88-105","publication_status":"published","publisher":"Cambridge University Press","article_type":"original","_id":"12612"},{"has_accepted_license":"1","type":"conference_abstract","oa_version":"Published Version","citation":{"ista":"Schlögl A, Kiss J. 2017. Scientific Computing at IST Austria. AHPC17 – Austrian HPC Meeting 2017. AHPC: Austrian HPC Meeting, 28.","chicago":"Schlögl, Alois, and Janos Kiss. “Scientific Computing at IST Austria.” In <i>AHPC17 – Austrian HPC Meeting 2017</i>, 28. FSP Scientific Computing, 2017.","short":"A. Schlögl, J. Kiss, in:, AHPC17 – Austrian HPC Meeting 2017, FSP Scientific Computing, 2017, p. 28.","ieee":"A. Schlögl and J. Kiss, “Scientific Computing at IST Austria,” in <i>AHPC17 – Austrian HPC Meeting 2017</i>, Grundlsee, Austria, 2017, p. 28.","apa":"Schlögl, A., &#38; Kiss, J. (2017). Scientific Computing at IST Austria. In <i>AHPC17 – Austrian HPC Meeting 2017</i> (p. 28). Grundlsee, Austria: FSP Scientific Computing.","mla":"Schlögl, Alois, and Janos Kiss. “Scientific Computing at IST Austria.” <i>AHPC17 – Austrian HPC Meeting 2017</i>, FSP Scientific Computing, 2017, p. 28.","ama":"Schlögl A, Kiss J. Scientific Computing at IST Austria. In: <i>AHPC17 – Austrian HPC Meeting 2017</i>. FSP Scientific Computing; 2017:28."},"date_created":"2023-05-05T12:58:53Z","year":"2017","publication":"AHPC17 – Austrian HPC Meeting 2017","month":"03","conference":{"location":"Grundlsee, Austria","start_date":"2017-03-01","name":"AHPC: Austrian HPC Meeting","end_date":"2017-03-03"},"author":[{"orcid":"0000-0002-5621-8100","first_name":"Alois","full_name":"Schlögl, Alois","last_name":"Schlögl","id":"45BF87EE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Janos","id":"3D3A06F8-F248-11E8-B48F-1D18A9856A87","full_name":"Kiss, Janos","last_name":"Kiss"}],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","file":[{"file_size":1005486,"date_created":"2023-05-16T07:20:50Z","content_type":"application/pdf","access_level":"open_access","creator":"dernst","file_id":"12969","relation":"main_file","file_name":"2017_AHPC_Schloegl.pdf","date_updated":"2023-05-16T07:20:50Z","checksum":"7bcc499479d4f4c5ce6c0071c24ca6c6","success":1}],"date_updated":"2023-05-16T07:22:23Z","_id":"12905","date_published":"2017-03-03T00:00:00Z","publisher":"FSP Scientific Computing","ddc":["000"],"file_date_updated":"2023-05-16T07:20:50Z","publication_status":"published","status":"public","page":"28","title":"Scientific Computing at IST Austria","oa":1,"main_file_link":[{"url":"https://vsc.ac.at/fileadmin/user_upload/vsc/conferences/ahpc17/BOOKLET_AHPC17.pdf","open_access":"1"}],"day":"03","department":[{"_id":"ScienComp"}]},{"quality_controlled":"1","pubrep_id":"717","month":"03","citation":{"ama":"Brázdil T, Chatterjee K, Forejt V, Kučera A. Trading performance for stability in Markov decision processes. <i>Journal of Computer and System Sciences</i>. 2017;84:144-170. doi:<a href=\"https://doi.org/10.1016/j.jcss.2016.09.009\">10.1016/j.jcss.2016.09.009</a>","apa":"Brázdil, T., Chatterjee, K., Forejt, V., &#38; Kučera, A. (2017). Trading performance for stability in Markov decision processes. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2016.09.009\">https://doi.org/10.1016/j.jcss.2016.09.009</a>","mla":"Brázdil, Tomáš, et al. “Trading Performance for Stability in Markov Decision Processes.” <i>Journal of Computer and System Sciences</i>, vol. 84, Elsevier, 2017, pp. 144–70, doi:<a href=\"https://doi.org/10.1016/j.jcss.2016.09.009\">10.1016/j.jcss.2016.09.009</a>.","short":"T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, Journal of Computer and System Sciences 84 (2017) 144–170.","ieee":"T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Trading performance for stability in Markov decision processes,” <i>Journal of Computer and System Sciences</i>, vol. 84. Elsevier, pp. 144–170, 2017.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Trading Performance for Stability in Markov Decision Processes.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.jcss.2016.09.009\">https://doi.org/10.1016/j.jcss.2016.09.009</a>.","ista":"Brázdil T, Chatterjee K, Forejt V, Kučera A. 2017. Trading performance for stability in Markov decision processes. Journal of Computer and System Sciences. 84, 144–170."},"oa_version":"Published Version","date_created":"2018-12-11T11:51:12Z","publication":"Journal of Computer and System Sciences","type":"journal_article","oa":1,"external_id":{"isi":["000388430000011"]},"day":"01","related_material":{"record":[{"status":"public","id":"2305","relation":"earlier_version"}]},"status":"public","isi":1,"doi":"10.1016/j.jcss.2016.09.009","date_published":"2017-03-01T00:00:00Z","intvolume":"        84","abstract":[{"lang":"eng","text":"We study controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize the expected mean-payoff performance and stability (also known as variability in the literature). We argue that the basic notion of expressing the stability using the statistical variance of the mean payoff is sometimes insufficient, and propose an alternative definition. We show that a strategy ensuring both the expected mean payoff and the variance below given bounds requires randomization and memory, under both the above definitions. We then show that the problem of finding such a strategy can be expressed as a set of constraints."}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","file":[{"date_updated":"2020-07-14T12:44:42Z","file_name":"IST-2016-717-v1+1_1-s2.0-S0022000016300897-main.pdf","checksum":"91271b23cf884d7c06d33bef0cd623b1","creator":"system","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"4885","date_created":"2018-12-12T10:11:30Z","file_size":708657}],"date_updated":"2023-09-20T11:15:31Z","author":[{"first_name":"Tomáš","full_name":"Brázdil, Tomáš","last_name":"Brázdil"},{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Vojtěch","full_name":"Forejt, Vojtěch","last_name":"Forejt"},{"first_name":"Antonín","full_name":"Kučera, Antonín","last_name":"Kučera"}],"language":[{"iso":"eng"}],"scopus_import":"1","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"year":"2017","has_accepted_license":"1","volume":84,"department":[{"_id":"KrCh"}],"title":"Trading performance for stability in Markov decision processes","page":"144 - 170","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"ddc":["004","006"],"publication_status":"published","file_date_updated":"2020-07-14T12:44:42Z","ec_funded":1,"_id":"1294","publisher":"Elsevier","publist_id":"6009"},{"volume":10205,"year":"2017","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2017-04-22","location":"Uppsala, Sweden","end_date":"2017-04-29"},"publication_identifier":{"isbn":["9783662545768"],"eisbn":["9783662545775"],"issn":["0302-9743"],"eissn":["1611-3349"]},"author":[{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","last_name":"Kretinsky","first_name":"Jan","orcid":"0000-0002-8122-2881"},{"orcid":"0000-0002-1712-2165","last_name":"Meggendorfer","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias","first_name":"Tobias"},{"first_name":"Clara","last_name":"Waldmann","full_name":"Waldmann, Clara"},{"first_name":"Maximilian","last_name":"Weininger","full_name":"Weininger, Maximilian"}],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Transforming deterministic ω\r\n-automata into deterministic parity automata is traditionally done using variants of appearance records. We present a more efficient variant of this approach, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and find out that our method produces smaller automata than previous approaches. Moreover, the experiments demonstrate the potential of our method for LTL synthesis, using LTL-to-Rabin translators. It leads to significantly smaller parity automata when compared to state-of-the-art approaches on complex formulae."}],"date_updated":"2023-06-21T13:29:46Z","article_processing_charge":"No","_id":"13160","publisher":"Springer","publication_status":"published","page":"443-460","title":"Index appearance record for transforming Rabin automata into parity automata","department":[{"_id":"KrCh"}],"alternative_title":["LNCS"],"type":"conference","date_created":"2023-06-21T13:21:14Z","citation":{"ista":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2017. Index appearance record for transforming Rabin automata into parity automata. Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10205, 443–460.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger. “Index Appearance Record for Transforming Rabin Automata into Parity Automata.” In <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, 10205:443–60. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">https://doi.org/10.1007/978-3-662-54577-5_26</a>.","ieee":"J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance record for transforming Rabin automata into parity automata,” in <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, Uppsala, Sweden, 2017, vol. 10205, pp. 443–460.","short":"J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, in:, Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2017, pp. 443–460.","apa":"Kretinsky, J., Meggendorfer, T., Waldmann, C., &#38; Weininger, M. (2017). Index appearance record for transforming Rabin automata into parity automata. In <i>Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 10205, pp. 443–460). Uppsala, Sweden: Springer. <a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">https://doi.org/10.1007/978-3-662-54577-5_26</a>","mla":"Kretinsky, Jan, et al. “Index Appearance Record for Transforming Rabin Automata into Parity Automata.” <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 10205, Springer, 2017, pp. 443–60, doi:<a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">10.1007/978-3-662-54577-5_26</a>.","ama":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record for transforming Rabin automata into parity automata. In: <i>Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 10205. Springer; 2017:443-460. doi:<a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">10.1007/978-3-662-54577-5_26</a>"},"oa_version":"Preprint","publication":"Tools and Algorithms for the Construction and Analysis of Systems","month":"03","arxiv":1,"acknowledgement":"This work is partially funded by the DFG project “Verified Model Checkers” and by the Czech Science Foundation, grant No. P202/12/G061.","quality_controlled":"1","intvolume":"     10205","doi":"10.1007/978-3-662-54577-5_26","date_published":"2017-03-31T00:00:00Z","status":"public","oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1701.05738","open_access":"1"}],"day":"31","external_id":{"arxiv":["1701.05738"]}},{"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2663-337X"]},"author":[{"first_name":"Fabienne","id":"4C8C26A4-F248-11E8-B48F-1D18A9856A87","last_name":"Jesse","full_name":"Jesse, Fabienne"}],"file":[{"file_size":3417773,"date_created":"2018-12-12T10:17:00Z","content_type":"application/pdf","access_level":"open_access","creator":"system","file_id":"5252","relation":"main_file","file_name":"IST-2017-857-v1+1_thesis_fabienne.pdf","date_updated":"2020-07-14T12:48:10Z","checksum":"c62257a7bff0c5f39e1abffc6bfcca5c"},{"file_id":"6212","relation":"source_file","access_level":"closed","content_type":"application/x-tex","creator":"dernst","file_size":215899,"date_created":"2019-04-05T08:51:59Z","checksum":"fc87d7d72fce52824a3ae7dcad0413a8","file_name":"2017_thesis_Jesse_source.tex","date_updated":"2020-07-14T12:48:10Z"}],"date_updated":"2023-09-07T12:01:21Z","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"text":"The lac operon is a classic model system for bacterial gene regulation, and has been studied extensively in E. coli, a classic model organism. However, not much is known about E. coli’s ecology and life outside the laboratory, in particular in soil and water environments. The natural diversity of the lac operon outside the laboratory, its role in the ecology of E. coli and the selection pressures it is exposed to, are similarly unknown.\r\nIn Chapter Two of this thesis, I explore the genetic diversity, phylogenetic history and signatures of selection of the lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia. I found that complete lac operons were present in all isolates examined, which in all but one case were functional. The lac operon phylogeny conformed to the whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal gene transfer as an explanation for the presence of functional lac operons in these clades. All lac operon genes showed a signature of purifying selection; this signature was strongest for the lacY gene. Lac operon genes of human and environmental isolates showed similar signatures of selection, except the lacZ gene, which showed a stronger signature of selection in environmental isolates.\r\nIn Chapter Three, I try to identify the natural genetic variation relevant for phenotype and fitness in the lac operon, comparing growth rate on lactose and LacZ activity of the lac operons of these wild isolates in a common genetic background. Sequence variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase binding motif, predicted variation in LacZ activity at full induction, using a thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation in LacZ activity, nor RNA polymerase binding predicted by the model correlated with variation in growth rate. Lac operons of human and environmental isolates did not differ systematically in either growth rate on lactose or LacZ protein activity, suggesting that these lac operons have been exposed to similar selection pressures. We thus have no evidence that the phenotypic variation we measured is relevant for fitness.\r\nTo start assessing the effect of genomic background on the growth phenotype conferred by the lac operon, I compared growth on minimal medium with lactose between lac operon constructs and the corresponding original isolates, I found that maximal growth rate was determined by genomic background, with almost all backgrounds conferring higher growth rates than lab strain K12 MG1655. However, I found no evidence that the lactose concentration at which growth was half maximal depended on genomic background.","lang":"eng"}],"has_accepted_license":"1","year":"2017","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"project":[{"name":"Selective Barriers to Horizontal Gene Transfer","call_identifier":"H2020","_id":"2578D616-B435-11E9-9278-68D0E5697425","grant_number":"648440"}],"supervisor":[{"first_name":"Jonathan P","id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","full_name":"Bollback, Jonathan P","last_name":"Bollback","orcid":"0000-0002-4624-4612"}],"page":"87","title":"The lac operon in the wild","department":[{"_id":"JoBo"}],"alternative_title":["ISTA Thesis"],"publist_id":"6829","publisher":"Institute of Science and Technology Austria","_id":"820","ec_funded":1,"file_date_updated":"2020-07-14T12:48:10Z","ddc":["576","577","579"],"publication_status":"published","pubrep_id":"857","month":"08","acknowledgement":"ERC H2020 programme (grant agreement no. 648440)\r\nThanks to Jon Bollback for giving me the chance to do this work, for sharing the ideas that lay at the basis of this work, for his honesty and openness, showing himself to me as a person and not just as a boss. Thanks to Nick Barton for his guidance at the last stage, reading and commenting extensively on several versions of this manuscript, and for his encouragement; thanks to both Jon and Nick for their kindness and patience. Thanks to Erik van Nimwegen and Calin Guet for their time and willingness to be in my thesis committee, and to Erik van Nimwegen especially for agreeing to enter my thesis committee at the last moment, and for his very sharp, helpful and relevant comments during and after the defense. Thanks to my collaborators and discussion partners: Anne Kupczok, for her guidance, ideas and discussions during the construction of the manuscript of Chapter Two, and her comments on the manuscript; Georg Rieckh for making me aware of the issue of parameter identifiability, suggesting how to solve it, and for his unfortunate idea to start the plasmid enterprise in the first place; Murat Tugrul for sharing his model, for his enthusiasm, and his comments on Chapter Three; Srdjan Sarikas for his collaboration on the Monod model fitting, fast forwarding the analysis to turbo speed and making beautiful figures, and making the discussion fun on top of it all; Vanessa Barone for her last minute comments, especially on Chapter Three, providing a sharp and very helpful experimentalist perspective at the last moment; Maros Pleska and Marjon de Vos for their comments on the manuscript of Chapter Two; Gasper Tkacik for his crucial input on the relation between growth rate and lactose concentration; Bor Kavcic for his input on growth rate modeling and error propagation. Thanks to the Bollback, Bollenbach, Barton, Guet and Tkacik group members for both pro- viding an inspiring and supportive scientific environment to work in, as well as a lot of warmth and colour to everyday life. And thanks to the friends I found here, to the people who were there for me and to the people who changed my life, making it stranger and more beautiful than I could have imagined, Maros, Vanessa, Tade, Suzi, Andrej, Peter, Tiago, Kristof, Karin, Irene, Misha, Mato, Guillaume and Zanin. ","type":"dissertation","degree_awarded":"PhD","date_created":"2018-12-11T11:48:41Z","citation":{"mla":"Jesse, Fabienne. <i>The Lac Operon in the Wild</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">10.15479/AT:ISTA:th_857</a>.","apa":"Jesse, F. (2017). <i>The lac operon in the wild</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">https://doi.org/10.15479/AT:ISTA:th_857</a>","ama":"Jesse F. The lac operon in the wild. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">10.15479/AT:ISTA:th_857</a>","ista":"Jesse F. 2017. The lac operon in the wild. Institute of Science and Technology Austria.","chicago":"Jesse, Fabienne. “The Lac Operon in the Wild.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_857\">https://doi.org/10.15479/AT:ISTA:th_857</a>.","short":"F. Jesse, The Lac Operon in the Wild, Institute of Science and Technology Austria, 2017.","ieee":"F. Jesse, “The lac operon in the wild,” Institute of Science and Technology Austria, 2017."},"oa_version":"Published Version","day":"25","oa":1,"doi":"10.15479/AT:ISTA:th_857","date_published":"2017-08-25T00:00:00Z","status":"public"}]