---
_id: '12432'
abstract:
- lang: eng
  text: "We present CertifyHAM, a deterministic algorithm that takes a graph G as
    input and either finds a Hamilton cycle of G or outputs that such a cycle does
    not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time
    of CertifyHAM is O(n/p) which is best possible. This improves upon previous results
    due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved
    analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively."
acknowledgement: "This project has received funding from the European Union’s Horizon
  2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement
  No 101034413"
article_processing_charge: No
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
citation:
  ama: 'Anastos M. Solving the Hamilton cycle problem fast on average. In: <i>63rd
    Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022-October.
    Institute of Electrical and Electronics Engineers; 2022:919-930. doi:<a href="https://doi.org/10.1109/FOCS54457.2022.00091">10.1109/FOCS54457.2022.00091</a>'
  apa: 'Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In
    <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022–October,
    pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics
    Engineers. <a href="https://doi.org/10.1109/FOCS54457.2022.00091">https://doi.org/10.1109/FOCS54457.2022.00091</a>'
  chicago: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.”
    In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022–October:919–30.
    Institute of Electrical and Electronics Engineers, 2022. <a href="https://doi.org/10.1109/FOCS54457.2022.00091">https://doi.org/10.1109/FOCS54457.2022.00091</a>.
  ieee: M. Anastos, “Solving the Hamilton cycle problem fast on average,” in <i>63rd
    Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United
    States, 2022, vol. 2022–October, pp. 919–930.
  ista: 'Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd
    Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of
    Computer Science vol. 2022–October, 919–930.'
  mla: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” <i>63rd
    Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022–October,
    Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:<a href="https://doi.org/10.1109/FOCS54457.2022.00091">10.1109/FOCS54457.2022.00091</a>.
  short: M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science,
    Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.
conference:
  end_date: 2022-11-03
  location: Denver, CO, United States
  name: 'FOCS: Foundations of Computer Science'
  start_date: 2022-10-31
corr_author: '1'
date_created: 2023-01-29T23:00:59Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2025-07-10T11:50:26Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS54457.2022.00091
ec_funded: 1
external_id:
  isi:
  - '000909382900084'
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 919-930
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: 63rd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - '9781665455190'
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving the Hamilton cycle problem fast on average
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022-October
year: '2022'
...
---
_id: '11145'
abstract:
- lang: eng
  text: List-decodability of Reed-Solomon codes has re-ceived a lot of attention,
    but the best-possible dependence between the parameters is still not well-understood.
    In this work, we focus on the case where the list-decoding radius is of the form
    r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon
    codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming
    ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate
    and list-decoding radius is best-possible for any code with list size less than
    exponential in the block length. By achieving this trade-off between rate and
    list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and
    Wootters, and resolve the main motivating question of their work. Moreover, while
    their result requires the field to be exponentially large in the block length,
    we only need the field size to be polynomially large (and in fact, almost-linear
    suffices). We deduce our main result from a more general theorem, in which we
    prove good list-decodability properties of random puncturings of any given code
    with very large distance.
article_processing_charge: No
arxiv: 1
author:
- first_name: Asaf
  full_name: Ferber, Asaf
  last_name: Ferber
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Lisa
  full_name: Sauermann, Lisa
  last_name: Sauermann
citation:
  ama: 'Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon
    codes. In: <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>.
    Vol 2022. IEEE; 2022:720-726. doi:<a href="https://doi.org/10.1109/FOCS52979.2021.00075">10.1109/FOCS52979.2021.00075</a>'
  apa: 'Ferber, A., Kwan, M. A., &#38; Sauermann, L. (2022). List-decodability with
    large radius for Reed-Solomon codes. In <i>62nd Annual IEEE Symposium on Foundations
    of Computer Science</i> (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE.
    <a href="https://doi.org/10.1109/FOCS52979.2021.00075">https://doi.org/10.1109/FOCS52979.2021.00075</a>'
  chicago: Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability
    with Large Radius for Reed-Solomon Codes.” In <i>62nd Annual IEEE Symposium on
    Foundations of Computer Science</i>, 2022:720–26. IEEE, 2022. <a href="https://doi.org/10.1109/FOCS52979.2021.00075">https://doi.org/10.1109/FOCS52979.2021.00075</a>.
  ieee: A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius
    for Reed-Solomon codes,” in <i>62nd Annual IEEE Symposium on Foundations of Computer
    Science</i>, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.
  ista: 'Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius
    for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer
    Science. FOCS: Foundations of Computer Science vol. 2022, 720–726.'
  mla: Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon
    Codes.” <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>,
    vol. 2022, IEEE, 2022, pp. 720–26, doi:<a href="https://doi.org/10.1109/FOCS52979.2021.00075">10.1109/FOCS52979.2021.00075</a>.
  short: A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations
    of Computer Science, IEEE, 2022, pp. 720–726.
conference:
  end_date: 2022-02-10
  location: Denver, CO, United States
  name: 'FOCS: Foundations of Computer Science'
  start_date: 2022-02-07
date_created: 2022-04-10T22:01:40Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2025-07-10T11:50:08Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS52979.2021.00075
external_id:
  arxiv:
  - '2012.10584'
  isi:
  - '000802209600065'
intvolume: '      2022'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2012.10584'
month: '02'
oa: 1
oa_version: Preprint
page: 720-726
publication: 62nd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - '9781665420556'
  issn:
  - 0272-5428
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '10775'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: List-decodability with large radius for Reed-Solomon codes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '11855'
abstract:
- lang: eng
  text: 'The decremental single-source shortest paths (SSSP) problem concerns maintaining
    the distances between a given source node s to every node in an n-node m-edge
    graph G undergoing edge deletions. While its static counterpart can be easily
    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 (JACM 1981) has been the fastest known algorithm
    for three decades. With the loss of a (1 + ε)-approximation factor, the running
    time was recently improved to O(n 2+o(1) ) by Bernstein and Roditty (SODA 2011),
    and more recently to O(n 1.8+o(1) + m 1+o(1) ) by Henzinger, Krinninger, and Nanongkai
    (SODA 2014). In this paper, we finally bring the running time of this case down
    to near-linear: We give a (1 + ε)-approximation algorithm with O(m 1+o(1) ) total
    update time, thus obtaining near-linear time. Moreover, we obtain O(m 1+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 log W) time is the O(mn 0.986 log
    W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works
    for the general weighted directed case. In contrast to the previous results which
    rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called
    sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature.
    A (d, ε)-hop set of a graph G = (V, E) is a set E'' of weighted edges such that
    the distance between any pair of nodes in G can be (1 + ε)-approximated by their
    d-hop distance (given by a path containing at most d edges) on G''=(V, E∪E'').
    Our algorithm can maintain an (n o(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 the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach
    tree. It results from extending and combining the monotone Even-Shiloach tree
    of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP
    technique of Bernstein (STOC 2013). These two new tools might be of independent
    interest.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger M, Krinninger S, Nanongkai D. Decremental single-source shortest
    paths on undirected graphs in near-linear total update time. In: <i>55th Annual
    Symposium on Foundations of Computer Science</i>. Institute of Electrical and
    Electronics Engineers; 2014:146-155. doi:<a href="https://doi.org/10.1109/focs.2014.24">10.1109/focs.2014.24</a>'
  apa: 'Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2014). Decremental single-source
    shortest paths on undirected graphs in near-linear total update time. In <i>55th
    Annual Symposium on Foundations of Computer Science</i> (pp. 146–155). Philadelphia,
    PA, United States: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/focs.2014.24">https://doi.org/10.1109/focs.2014.24</a>'
  chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Decremental
    Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update
    Time.” In <i>55th Annual Symposium on Foundations of Computer Science</i>, 146–55.
    Institute of Electrical and Electronics Engineers, 2014. <a href="https://doi.org/10.1109/focs.2014.24">https://doi.org/10.1109/focs.2014.24</a>.
  ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source
    shortest paths on undirected graphs in near-linear total update time,” in <i>55th
    Annual Symposium on Foundations of Computer Science</i>, Philadelphia, PA, United
    States, 2014, pp. 146–155.
  ista: 'Henzinger M, Krinninger S, Nanongkai D. 2014. Decremental single-source shortest
    paths on undirected graphs in near-linear total update time. 55th Annual Symposium
    on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer
    Science, 146–155.'
  mla: Henzinger, Monika, et al. “Decremental Single-Source Shortest Paths on Undirected
    Graphs in near-Linear Total Update Time.” <i>55th Annual Symposium on Foundations
    of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2014,
    pp. 146–55, doi:<a href="https://doi.org/10.1109/focs.2014.24">10.1109/focs.2014.24</a>.
  short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 55th Annual Symposium on
    Foundations of Computer Science, Institute of Electrical and Electronics Engineers,
    2014, pp. 146–155.
conference:
  end_date: 2014-10-21
  location: Philadelphia, PA, United States
  name: 'FOCS: Annual Symposium on Foundations of Computer Science'
  start_date: 2014-10-18
date_created: 2022-08-16T08:14:33Z
date_published: 2014-10-01T00:00:00Z
date_updated: 2024-11-06T12:18:18Z
day: '01'
doi: 10.1109/focs.2014.24
extern: '1'
external_id:
  arxiv:
  - '1402.0054'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1402.0054
month: '10'
oa: 1
oa_version: Preprint
page: 146-155
publication: 55th Annual Symposium on Foundations of Computer Science
publication_identifier:
  eisbn:
  - 978-1-4799-6517-5
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
  record:
  - id: '11768'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Decremental single-source shortest paths on undirected graphs in near-linear
  total update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '11856'
abstract:
- lang: eng
  text: 'We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest
    paths problem in unweighted undirected n-node m-edge graphs under edge deletions.
    The fastest algorithm for this problem is a randomized algorithm with a total
    update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004).
    The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach
    (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We
    improve these results as follows: (1) We present an algorithm with a total update
    time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in
    addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time
    when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in
    the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial
    algorithm with 1 + ϵ multiplicative error cannot have an additive error less than
    2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor,
    Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska
    Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 +
    ϵ)-approximation algorithm (without an additive error) with the same time guarantees,
    improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n))
    ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation
    and time guarantees. (2) We present a deterministic algorithm with a total update
    time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative
    error of 1 + ϵ and gives the first improved deterministic algorithm since 1981.
    It also answers an open question raised by Bernstein in his STOC 2013 paper. In
    order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach
    tree algorithm which maintains a bounded-distance shortest-paths tree on a certain
    type of emulator called locally persevering emulator. (2) A derandomization technique
    based on moving Even-Shiloach trees as a way to derandomize the standard random
    set argument. These techniques might be of independent interest.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest
    paths: Breaking the O(mn) barrier and derandomization. In: <i>54th Annual Symposium
    on Foundations of Computer Science</i>. Institute of Electrical and Electronics
    Engineers; 2013:538-547. doi:<a href="https://doi.org/10.1109/focs.2013.64">10.1109/focs.2013.64</a>'
  apa: 'Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2013). Dynamic approximate
    all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In <i>54th
    Annual Symposium on Foundations of Computer Science</i> (pp. 538–547). Berkeley,
    CA, United States: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/focs.2013.64">https://doi.org/10.1109/focs.2013.64</a>'
  chicago: 'Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic
    Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.”
    In <i>54th Annual Symposium on Foundations of Computer Science</i>, 538–47. Institute
    of Electrical and Electronics Engineers, 2013. <a href="https://doi.org/10.1109/focs.2013.64">https://doi.org/10.1109/focs.2013.64</a>.'
  ieee: 'M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs
    shortest paths: Breaking the O(mn) barrier and derandomization,” in <i>54th Annual
    Symposium on Foundations of Computer Science</i>, Berkeley, CA, United States,
    2013, pp. 538–547.'
  ista: 'Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs
    shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium
    on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer
    Science, 538–547.'
  mla: 'Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking
    the O(Mn) Barrier and Derandomization.” <i>54th Annual Symposium on Foundations
    of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2013,
    pp. 538–47, doi:<a href="https://doi.org/10.1109/focs.2013.64">10.1109/focs.2013.64</a>.'
  short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 54th Annual Symposium on
    Foundations of Computer Science, Institute of Electrical and Electronics Engineers,
    2013, pp. 538–547.
conference:
  end_date: 2013-10-29
  location: Berkeley, CA, United States
  name: 'FOCS: Symposium on Foundations of Computer Science'
  start_date: 2013-10-26
date_created: 2022-08-16T08:22:37Z
date_published: 2013-10-01T00:00:00Z
date_updated: 2024-11-06T12:18:28Z
day: '01'
doi: 10.1109/focs.2013.64
extern: '1'
external_id:
  arxiv:
  - '1308.0776'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1308.0776
month: '10'
oa: 1
oa_version: Preprint
page: 538-547
publication: 54th Annual Symposium on Foundations of Computer Science
publication_identifier:
  eisbn:
  - 978-0-7695-5135-7
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and
  derandomization'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '11682'
abstract:
- lang: eng
  text: We consider the parametric minimum spanning tree problem, in which we are
    given a graph with edge weights that are linear functions of a parameter /spl
    lambda/ and wish to compute the sequence of minimum spanning trees generated as
    /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem,
    in which /spl lambda/ represents time and the graph is subject in addition to
    changes such as edge insertions, deletions, and modifications of the weight functions
    as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per
    combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per
    change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup
    1/2/log n) randomized) for planar graphs or other minor-closed families of graphs,
    and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for
    planar graphs with weight changes but no insertions or deletions.
article_processing_charge: No
author:
- first_name: P. K.
  full_name: Agarwal, P. K.
  last_name: Agarwal
- first_name: D.
  full_name: EppsteinL. J. Guibas, D.
  last_name: EppsteinL. J. Guibas
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Agarwal PK, EppsteinL. J. Guibas D, Henzinger M. Parametric and kinetic minimum
    spanning trees. In: <i>Proceedings of the 39th Annual Symposium on Foundations
    of Computer Science</i>. ; 1998:596-605. doi:<a href="https://doi.org/10.1109/SFCS.1998.743510">10.1109/SFCS.1998.743510</a>'
  apa: Agarwal, P. K., EppsteinL. J. Guibas, D., &#38; Henzinger, M. (1998). Parametric
    and kinetic minimum spanning trees. In <i>Proceedings of the 39th Annual Symposium
    on Foundations of Computer Science</i> (pp. 596–605). Palo Alto, CA, United States.
    <a href="https://doi.org/10.1109/SFCS.1998.743510">https://doi.org/10.1109/SFCS.1998.743510</a>
  chicago: Agarwal, P. K., D. EppsteinL. J. Guibas, and Monika Henzinger. “Parametric
    and Kinetic Minimum Spanning Trees.” In <i>Proceedings of the 39th Annual Symposium
    on Foundations of Computer Science</i>, 596–605, 1998. <a href="https://doi.org/10.1109/SFCS.1998.743510">https://doi.org/10.1109/SFCS.1998.743510</a>.
  ieee: P. K. Agarwal, D. EppsteinL. J. Guibas, and M. Henzinger, “Parametric and
    kinetic minimum spanning trees,” in <i>Proceedings of the 39th Annual Symposium
    on Foundations of Computer Science</i>, Palo Alto, CA, United States, 1998, pp.
    596–605.
  ista: Agarwal PK, EppsteinL. J. Guibas D, Henzinger M. 1998. Parametric and kinetic
    minimum spanning trees. Proceedings of the 39th Annual Symposium on Foundations
    of Computer Science. Annual IEEE Symposium on Foundations of Computer Science,
    596–605.
  mla: Agarwal, P. K., et al. “Parametric and Kinetic Minimum Spanning Trees.” <i>Proceedings
    of the 39th Annual Symposium on Foundations of Computer Science</i>, 1998, pp.
    596–605, doi:<a href="https://doi.org/10.1109/SFCS.1998.743510">10.1109/SFCS.1998.743510</a>.
  short: P.K. Agarwal, D. EppsteinL. J. Guibas, M. Henzinger, in:, Proceedings of
    the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 596–605.
conference:
  end_date: 1998-11-11
  location: Palo Alto, CA, United States
  name: Annual IEEE Symposium on Foundations of Computer Science
  start_date: 1998-11-08
date_created: 2022-07-28T07:21:34Z
date_published: 1998-09-01T00:00:00Z
date_updated: 2024-11-06T12:08:31Z
day: '01'
doi: 10.1109/SFCS.1998.743510
extern: '1'
language:
- iso: eng
month: '09'
oa_version: None
page: 596-605
publication: Proceedings of the 39th Annual Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - 0-8186-9172-7
  issn:
  - 0272-5428
publication_status: published
quality_controlled: '1'
scopus_import: '1'
status: public
title: Parametric and kinetic minimum spanning trees
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1998'
...
---
_id: '11684'
abstract:
- lang: eng
  text: 'This paper presents an algorithm for the fully dynamic biconnectivity problem
    whose running time is exponentially faster than all previously known solutions.
    It is the first dynamic algorithm that answers biconnectivity queries in time
    O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or
    deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized
    algorithm with the update time amortized update time O(log/sup 4/n). Only recently
    the best deterministic result for this problem was improved to O(/spl radic/nlog/sup
    2/n). We also give the first fully dynamic and a novel deletions-only transitive
    closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo
    algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the
    average number of edges in the graph during the whole update sequence: The fully
    dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl
    radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup
    /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is
    the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The
    deletions-only algorithm answers queries in time O(n/logn). Its amortized update
    time is O(nlog/sup 2/n).'
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: V.
  full_name: King, V.
  last_name: King
citation:
  ama: 'Henzinger M, King V. Fully dynamic biconnectivity and transitive closure.
    In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>. Institute
    of Electrical and Electronics Engineers; 1995:664-672. doi:<a href="https://doi.org/10.1109/SFCS.1995.492668">10.1109/SFCS.1995.492668</a>'
  apa: 'Henzinger, M., &#38; King, V. (1995). Fully dynamic biconnectivity and transitive
    closure. In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>
    (pp. 664–672). Milwaukee, WI, United States: Institute of Electrical and Electronics
    Engineers. <a href="https://doi.org/10.1109/SFCS.1995.492668">https://doi.org/10.1109/SFCS.1995.492668</a>'
  chicago: Henzinger, Monika, and V. King. “Fully Dynamic Biconnectivity and Transitive
    Closure.” In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>,
    664–72. Institute of Electrical and Electronics Engineers, 1995. <a href="https://doi.org/10.1109/SFCS.1995.492668">https://doi.org/10.1109/SFCS.1995.492668</a>.
  ieee: M. Henzinger and V. King, “Fully dynamic biconnectivity and transitive closure,”
    in <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, Milwaukee,
    WI, United States, 1995, pp. 664–672.
  ista: Henzinger M, King V. 1995. Fully dynamic biconnectivity and transitive closure.
    Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of
    Computer Science, 664–672.
  mla: Henzinger, Monika, and V. King. “Fully Dynamic Biconnectivity and Transitive
    Closure.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>,
    Institute of Electrical and Electronics Engineers, 1995, pp. 664–72, doi:<a href="https://doi.org/10.1109/SFCS.1995.492668">10.1109/SFCS.1995.492668</a>.
  short: M. Henzinger, V. King, in:, Proceedings of IEEE 36th Annual Foundations of
    Computer Science, Institute of Electrical and Electronics Engineers, 1995, pp.
    664–672.
conference:
  end_date: 1995-10-25
  location: Milwaukee, WI, United States
  name: Foundations of Computer Science
  start_date: 1995-10-23
date_created: 2022-07-28T11:28:13Z
date_published: 1995-11-01T00:00:00Z
date_updated: 2024-11-04T11:41:41Z
day: '01'
doi: 10.1109/SFCS.1995.492668
extern: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 664-672
publication: Proceedings of IEEE 36th Annual Foundations of Computer Science
publication_identifier:
  isbn:
  - 0-8186-7183-1
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic biconnectivity and transitive closure
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1995'
...
---
_id: '4034'
abstract:
- lang: eng
  text: Any arbitrary polyhedron P contained as a subset within Rd can be written
    as algebraic sum of simple terms, each an integer multiple of the intersection
    of d or fewer half-spaces defined by facets of P. P can be non-convex and can
    have holes of any kind. Among the consequences of this result are a short boolean
    formula for P, a fast parallel algorithm for point classification, and a new proof
    of the Gram-Sommerville angle relation.
acknowledgement: The author thanks Bei-Fang Chen, Siu-Wing Cheng, David Dobkin, Nikolai
  Dolbilin, Ping Fu, Sergei Ryshkov, and Vadim Shapiro for discussions on the topic
  of this paper.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: 'Edelsbrunner H. Algebraic decomposition of non-convex polyhedra. In: <i>Proceedings
    of IEEE 36th Annual Foundations of Computer Science</i>. IEEE; 1995:248-257.'
  apa: 'Edelsbrunner, H. (1995). Algebraic decomposition of non-convex polyhedra.
    In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i> (pp.
    248–257). Milwaukee, WI, United States of America: IEEE.'
  chicago: Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.”
    In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, 248–57.
    IEEE, 1995.
  ieee: H. Edelsbrunner, “Algebraic decomposition of non-convex polyhedra,” in <i>Proceedings
    of IEEE 36th Annual Foundations of Computer Science</i>, Milwaukee, WI, United
    States of America, 1995, pp. 248–257.
  ista: 'Edelsbrunner H. 1995. Algebraic decomposition of non-convex polyhedra. Proceedings
    of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer
    Science, 248–257.'
  mla: Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.” <i>Proceedings
    of IEEE 36th Annual Foundations of Computer Science</i>, IEEE, 1995, pp. 248–57.
  short: H. Edelsbrunner, in:, Proceedings of IEEE 36th Annual Foundations of Computer
    Science, IEEE, 1995, pp. 248–257.
conference:
  end_date: 1995-10-25
  location: Milwaukee, WI, United States of America
  name: 'FOCS: Foundations of Computer Science'
  start_date: 1995-10-23
date_created: 2018-12-11T12:06:33Z
date_published: 1995-10-01T00:00:00Z
date_updated: 2022-06-13T12:27:11Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/abstract/document/492480
month: '10'
oa_version: None
page: 248 - 257
publication: Proceedings of IEEE 36th Annual Foundations of Computer Science
publication_identifier:
  issn:
  - 0272-5428
publication_status: published
publisher: IEEE
publist_id: '2093'
quality_controlled: '1'
status: public
title: Algebraic decomposition of non-convex polyhedra
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1995'
...
---
_id: '4498'
abstract:
- lang: eng
  text: We present algorithms for computing similarity relations of labeled graphs.
    Similarity relations have applications for the refinement and verification of
    reactive systems. For finite graphs, we present an O(mn) algorithm for computing
    the similarity relation of a graph with n vertices and m edges (assuming m⩾n).
    For effectively presented infinite graphs, we present a symbolic similarity-checking
    procedure that terminates if a finite similarity relation exists. We show that
    2D rectangular automata, which model discrete reactive systems with continuous
    environments, define effectively presented infinite graphs with finite similarity
    relations. It follows that the refinement problem and the ∀CTL* model-checking
    problem are decidable for 2D rectangular automata
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Peter
  full_name: Kopke, Peter
  last_name: Kopke
citation:
  ama: 'Henzinger M, Henzinger TA, Kopke P. Computing simulations on finite and infinite
    graphs. In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>.
    IEEE; 1995:453-462. doi:<a href="https://doi.org/10.1109/SFCS.1995.492576">10.1109/SFCS.1995.492576</a>'
  apa: 'Henzinger, M., Henzinger, T. A., &#38; Kopke, P. (1995). Computing simulations
    on finite and infinite graphs. In <i>Proceedings of IEEE 36th Annual Foundations
    of Computer Science</i> (pp. 453–462). Milwaukee, WI, United States of America:
    IEEE. <a href="https://doi.org/10.1109/SFCS.1995.492576">https://doi.org/10.1109/SFCS.1995.492576</a>'
  chicago: Henzinger, Monika, Thomas A Henzinger, and Peter Kopke. “Computing Simulations
    on Finite and Infinite Graphs.” In <i>Proceedings of IEEE 36th Annual Foundations
    of Computer Science</i>, 453–62. IEEE, 1995. <a href="https://doi.org/10.1109/SFCS.1995.492576">https://doi.org/10.1109/SFCS.1995.492576</a>.
  ieee: M. Henzinger, T. A. Henzinger, and P. Kopke, “Computing simulations on finite
    and infinite graphs,” in <i>Proceedings of IEEE 36th Annual Foundations of Computer
    Science</i>, Milwaukee, WI, United States of America, 1995, pp. 453–462.
  ista: 'Henzinger M, Henzinger TA, Kopke P. 1995. Computing simulations on finite
    and infinite graphs. Proceedings of IEEE 36th Annual Foundations of Computer Science.
    FOCS: Foundations of Computer Science, 453–462.'
  mla: Henzinger, Monika, et al. “Computing Simulations on Finite and Infinite Graphs.”
    <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>, IEEE,
    1995, pp. 453–62, doi:<a href="https://doi.org/10.1109/SFCS.1995.492576">10.1109/SFCS.1995.492576</a>.
  short: M. Henzinger, T.A. Henzinger, P. Kopke, in:, Proceedings of IEEE 36th Annual
    Foundations of Computer Science, IEEE, 1995, pp. 453–462.
conference:
  end_date: 1995-10-25
  location: Milwaukee, WI, United States of America
  name: 'FOCS: Foundations of Computer Science'
  start_date: 1995-10-23
date_created: 2018-12-11T12:09:10Z
date_published: 1995-11-01T00:00:00Z
date_updated: 2024-11-06T12:02:08Z
day: '01'
doi: 10.1109/SFCS.1995.492576
extern: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 453 - 462
publication: Proceedings of IEEE 36th Annual Foundations of Computer Science
publication_identifier:
  isbn:
  - '0818671831'
  issn:
  - 0272-5428
publication_status: published
publisher: IEEE
publist_id: '231'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing simulations on finite and infinite graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1995'
...
---
_id: '3514'
abstract:
- lang: eng
  text: We consider the problem of obtaining sharp (nearly quadratic) bounds for the
    combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection
    of n bivariate (or generally multi-variate) continuous and &quot;simple&quot;
    functions, and of designing efficient algorithms for the calculation of this envelope.
    This problem generalizes the well-studied univariate case (whose analysis is based
    on the theory of Davenport-Schinzel sequences), but appears to be much more difficult
    and still largely unsolved. It is a central problem that arises in many areas
    in computational and combinatorial geometry, and has numerous applications including
    generalized planar Voronoi diagrams, hidden surface elimination for intersecting
    surfaces, purely translational motion planning, finding common transversals of
    polyhedra, and more. In this abstract we provide several partial solutions and
    generalizations of this problem, and apply them to the problems mentioned above.
    The most significant of our results is that the lower envelope of n triangles
    in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n)
    is the extremely slowly growing inverse of Ackermann's function), that this bound
    is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: János
  full_name: Pach, János
  last_name: Pach
- first_name: Jacob
  full_name: Schwartz, Jacob
  last_name: Schwartz
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Pach J, Schwartz J, Sharir M. On the lower envelope of bivariate
    functions and its applications. In: <i>28th Annual Symposium on Foundations of
    Computer Science </i>. IEEE; 1987:27-37. doi:<a href="https://doi.org/10.1109/SFCS.1987.44">10.1109/SFCS.1987.44</a>'
  apa: 'Edelsbrunner, H., Pach, J., Schwartz, J., &#38; Sharir, M. (1987). On the
    lower envelope of bivariate functions and its applications. In <i>28th Annual
    Symposium on Foundations of Computer Science </i> (pp. 27–37). Los Angeles, CA,
    USA: IEEE. <a href="https://doi.org/10.1109/SFCS.1987.44">https://doi.org/10.1109/SFCS.1987.44</a>'
  chicago: Edelsbrunner, Herbert, János Pach, Jacob Schwartz, and Micha Sharir. “On
    the Lower Envelope of Bivariate Functions and Its Applications.” In <i>28th Annual
    Symposium on Foundations of Computer Science </i>, 27–37. IEEE, 1987. <a href="https://doi.org/10.1109/SFCS.1987.44">https://doi.org/10.1109/SFCS.1987.44</a>.
  ieee: H. Edelsbrunner, J. Pach, J. Schwartz, and M. Sharir, “On the lower envelope
    of bivariate functions and its applications,” in <i>28th Annual Symposium on Foundations
    of Computer Science </i>, Los Angeles, CA, USA, 1987, pp. 27–37.
  ista: 'Edelsbrunner H, Pach J, Schwartz J, Sharir M. 1987. On the lower envelope
    of bivariate functions and its applications. 28th Annual Symposium on Foundations
    of Computer Science . FOCS: Foundations of Computer Science, 27–37.'
  mla: Edelsbrunner, Herbert, et al. “On the Lower Envelope of Bivariate Functions
    and Its Applications.” <i>28th Annual Symposium on Foundations of Computer Science
    </i>, IEEE, 1987, pp. 27–37, doi:<a href="https://doi.org/10.1109/SFCS.1987.44">10.1109/SFCS.1987.44</a>.
  short: H. Edelsbrunner, J. Pach, J. Schwartz, M. Sharir, in:, 28th Annual Symposium
    on Foundations of Computer Science , IEEE, 1987, pp. 27–37.
conference:
  end_date: 1987-10-14
  location: Los Angeles, CA, USA
  name: 'FOCS: Foundations of Computer Science'
  start_date: 1987-10-12
date_created: 2018-12-11T12:03:44Z
date_published: 1987-10-14T00:00:00Z
date_updated: 2022-02-07T15:14:55Z
day: '14'
doi: 10.1109/SFCS.1987.44
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/4568253?denied=
month: '10'
oa_version: None
page: 27 - 37
publication: '28th Annual Symposium on Foundations of Computer Science '
publication_identifier:
  isbn:
  - 0-8186-0807-2
  issn:
  - 0272-5428
publication_status: published
publisher: IEEE
publist_id: '2871'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the lower envelope of bivariate functions and its applications
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1987'
...