---
OA_place: publisher
OA_type: hybrid
_id: '19440'
abstract:
- lang: eng
  text: Let μ(G) denote the minimum number of edges whose addition to G results in
    a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition
    to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in
    the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there
    exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if
    G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n.
    Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on
    μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random
    graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability,
    μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p)
    and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial
    time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability,
    the algorithm returns a set of edges of size μ(G) whose addition to G results
    in a pancyclic (and therefore also Hamiltonian) graph.
acknowledgement: The authors would like to express their thanks to the referees of
  the article for their valuable input towards improving the presentation of our result.
  This project has received funding from the European Union's Horizon 2020 research
  and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.
article_number: e21286
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Yahav
  full_name: Alon, Yahav
  last_name: Alon
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
citation:
  ama: Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity
    in random graphs. <i>Random Structures and Algorithms</i>. 2025;66(2). doi:<a
    href="https://doi.org/10.1002/rsa.21286">10.1002/rsa.21286</a>
  apa: Alon, Y., &#38; Anastos, M. (2025). The completion numbers of hamiltonicity
    and pancyclicity in random graphs. <i>Random Structures and Algorithms</i>. Wiley.
    <a href="https://doi.org/10.1002/rsa.21286">https://doi.org/10.1002/rsa.21286</a>
  chicago: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity
    and Pancyclicity in Random Graphs.” <i>Random Structures and Algorithms</i>. Wiley,
    2025. <a href="https://doi.org/10.1002/rsa.21286">https://doi.org/10.1002/rsa.21286</a>.
  ieee: Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity
    in random graphs,” <i>Random Structures and Algorithms</i>, vol. 66, no. 2. Wiley,
    2025.
  ista: Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity
    in random graphs. Random Structures and Algorithms. 66(2), e21286.
  mla: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity
    and Pancyclicity in Random Graphs.” <i>Random Structures and Algorithms</i>, vol.
    66, no. 2, e21286, Wiley, 2025, doi:<a href="https://doi.org/10.1002/rsa.21286">10.1002/rsa.21286</a>.
  short: Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025).
date_created: 2025-03-23T23:01:26Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-09-30T11:15:41Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1002/rsa.21286
ec_funded: 1
external_id:
  arxiv:
  - '2304.03710'
  isi:
  - '001420226800001'
file:
- access_level: open_access
  checksum: 6067747e805fa356d560dc45f2a89918
  content_type: application/pdf
  creator: dernst
  date_created: 2025-03-25T11:46:27Z
  date_updated: 2025-03-25T11:46:27Z
  file_id: '19459'
  file_name: 2025_RandomStruc_Alon.pdf
  file_size: 549236
  relation: main_file
  success: 1
file_date_updated: 2025-03-25T11:46:27Z
has_accepted_license: '1'
intvolume: '        66'
isi: 1
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The completion numbers of hamiltonicity and pancyclicity in random graphs
tmp:
  image: /images/cc_by_nc.png
  legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
  short: CC BY-NC (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 66
year: '2025'
...
---
_id: '11706'
abstract:
- lang: eng
  text: 'We say that (Formula presented.) if, in every edge coloring (Formula presented.),
    we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy
    of (Formula presented.). The well-known states that the threshold for the property
    (Formula presented.) is equal to (Formula presented.), where (Formula presented.)
    is given by (Formula presented.) for any pair of graphs (Formula presented.) and
    (Formula presented.) with (Formula presented.). In this article, we show the 0-statement
    of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques. '
acknowledgement: "This work was started at the thematic program GRAPHS@IMPA (January–March
  2018), in Rio de Janeiro. We thank IMPA and the organisers for the hospitality and
  for providing a pleasant research environment. We thank Rob Morris for helpful discussions,
  and the anonymous referees for their careful reading and many helpful suggestions.
  Open Access funding enabled and organized by Projekt DEAL.\r\nA. Liebenau was supported
  by an ARC DECRA Fellowship Grant DE170100789. L. Mattos was supported by CAPES and
  by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's
  Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1,
  project ID: 390685689). W. Mendonça was supported by CAPES project 88882.332408/2010-01."
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Anita
  full_name: Liebenau, Anita
  last_name: Liebenau
- first_name: Letícia
  full_name: Mattos, Letícia
  last_name: Mattos
- first_name: Walner
  full_name: Mendonca Dos Santos, Walner
  id: 12c6bd4d-2cd0-11ec-a0da-e28f42f65ebd
  last_name: Mendonca Dos Santos
- first_name: Jozef
  full_name: Skokan, Jozef
  last_name: Skokan
citation:
  ama: Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. Asymmetric Ramsey properties
    of random graphs involving cliques and cycles. <i>Random Structures and Algorithms</i>.
    2023;62(4):1035-1055. doi:<a href="https://doi.org/10.1002/rsa.21106">10.1002/rsa.21106</a>
  apa: Liebenau, A., Mattos, L., Mendonca dos Santos, W., &#38; Skokan, J. (2023).
    Asymmetric Ramsey properties of random graphs involving cliques and cycles. <i>Random
    Structures and Algorithms</i>. Wiley. <a href="https://doi.org/10.1002/rsa.21106">https://doi.org/10.1002/rsa.21106</a>
  chicago: Liebenau, Anita, Letícia Mattos, Walner Mendonca dos Santos, and Jozef
    Skokan. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.”
    <i>Random Structures and Algorithms</i>. Wiley, 2023. <a href="https://doi.org/10.1002/rsa.21106">https://doi.org/10.1002/rsa.21106</a>.
  ieee: A. Liebenau, L. Mattos, W. Mendonca dos Santos, and J. Skokan, “Asymmetric
    Ramsey properties of random graphs involving cliques and cycles,” <i>Random Structures
    and Algorithms</i>, vol. 62, no. 4. Wiley, pp. 1035–1055, 2023.
  ista: Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. 2023. Asymmetric Ramsey
    properties of random graphs involving cliques and cycles. Random Structures and
    Algorithms. 62(4), 1035–1055.
  mla: Liebenau, Anita, et al. “Asymmetric Ramsey Properties of Random Graphs Involving
    Cliques and Cycles.” <i>Random Structures and Algorithms</i>, vol. 62, no. 4,
    Wiley, 2023, pp. 1035–55, doi:<a href="https://doi.org/10.1002/rsa.21106">10.1002/rsa.21106</a>.
  short: A. Liebenau, L. Mattos, W. Mendonca dos Santos, J. Skokan, Random Structures
    and Algorithms 62 (2023) 1035–1055.
date_created: 2022-07-31T22:01:49Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-10-04T09:38:45Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1002/rsa.21106
external_id:
  isi:
  - '000828530400001'
file:
- access_level: open_access
  checksum: 3a5969d0c512aef01c30f3dc81c6d59b
  content_type: application/pdf
  creator: dernst
  date_created: 2023-10-04T09:37:26Z
  date_updated: 2023-10-04T09:37:26Z
  file_id: '14389'
  file_name: 2023_RandomStructureAlgorithms_Liebenau.pdf
  file_size: 1362334
  relation: main_file
  success: 1
file_date_updated: 2023-10-04T09:37:26Z
has_accepted_license: '1'
intvolume: '        62'
isi: 1
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 1035-1055
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Asymmetric Ramsey properties of random graphs involving cliques and cycles
tmp:
  image: /images/cc_by_nc.png
  legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
  short: CC BY-NC (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2023'
...
---
_id: '9565'
abstract:
- lang: eng
  text: Let D(n,p) be the random directed graph on n vertices where each of the n(n-1)
    possible arcs is present independently with probability p. A celebrated result
    of Frieze shows that if p≥(logn+ω(1))/n then D(n,p) typically has a directed Hamilton
    cycle, and this is best possible. In this paper, we obtain a strengthening of
    this result, showing that under the same condition, the number of directed Hamilton
    cycles in D(n,p) is typically n!(p(1+o(1)))n. We also prove a hitting-time version
    of this statement, showing that in the random directed graph process, as soon
    as every vertex has in-/out-degrees at least 1, there are typically n!(logn/n(1+o(1)))n
    directed Hamilton cycles.
article_processing_charge: No
article_type: original
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: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
citation:
  ama: Ferber A, Kwan MA, Sudakov B. Counting Hamilton cycles in sparse random directed
    graphs. <i>Random Structures and Algorithms</i>. 2018;53(4):592-603. doi:<a href="https://doi.org/10.1002/rsa.20815">10.1002/rsa.20815</a>
  apa: Ferber, A., Kwan, M. A., &#38; Sudakov, B. (2018). Counting Hamilton cycles
    in sparse random directed graphs. <i>Random Structures and Algorithms</i>. Wiley.
    <a href="https://doi.org/10.1002/rsa.20815">https://doi.org/10.1002/rsa.20815</a>
  chicago: Ferber, Asaf, Matthew Alan Kwan, and Benny Sudakov. “Counting Hamilton
    Cycles in Sparse Random Directed Graphs.” <i>Random Structures and Algorithms</i>.
    Wiley, 2018. <a href="https://doi.org/10.1002/rsa.20815">https://doi.org/10.1002/rsa.20815</a>.
  ieee: A. Ferber, M. A. Kwan, and B. Sudakov, “Counting Hamilton cycles in sparse
    random directed graphs,” <i>Random Structures and Algorithms</i>, vol. 53, no.
    4. Wiley, pp. 592–603, 2018.
  ista: Ferber A, Kwan MA, Sudakov B. 2018. Counting Hamilton cycles in sparse random
    directed graphs. Random Structures and Algorithms. 53(4), 592–603.
  mla: Ferber, Asaf, et al. “Counting Hamilton Cycles in Sparse Random Directed Graphs.”
    <i>Random Structures and Algorithms</i>, vol. 53, no. 4, Wiley, 2018, pp. 592–603,
    doi:<a href="https://doi.org/10.1002/rsa.20815">10.1002/rsa.20815</a>.
  short: A. Ferber, M.A. Kwan, B. Sudakov, Random Structures and Algorithms 53 (2018)
    592–603.
date_created: 2021-06-18T12:06:28Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-02-23T14:01:03Z
day: '01'
doi: 10.1002/rsa.20815
extern: '1'
external_id:
  arxiv:
  - '1708.07746'
intvolume: '        53'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1708.07746
month: '12'
oa: 1
oa_version: Preprint
page: 592-603
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting Hamilton cycles in sparse random directed graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 53
year: '2018'
...
---
_id: '9567'
abstract:
- lang: eng
  text: Let P be a graph property which is preserved by removal of edges, and consider
    the random graph process that starts with the empty n-vertex graph and then adds
    edges one-by-one, each chosen uniformly at random subject to the constraint that
    P is not violated. These types of random processes have been the subject of extensive
    research over the last 20 years, having striking applications in extremal combinatorics,
    and leading to the discovery of important probabilistic tools. In this paper we
    consider the k-matching-free process, where P is the property of not containing
    a matching of size k. We are able to analyse the behaviour of this process for
    a wide range of values of k; in particular we prove that if k=o(n) or if n−2k=o(n−−√/logn)
    then this process is likely to terminate in a k-matching-free graph with the maximum
    possible number of edges, as characterised by Erdős and Gallai. We also show that
    these bounds on k are essentially best possible, and we make a first step towards
    understanding the behaviour of the process in the intermediate regime.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Krivelevich, Michael
  last_name: Krivelevich
- 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: Po‐Shen
  full_name: Loh, Po‐Shen
  last_name: Loh
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
citation:
  ama: Krivelevich M, Kwan MA, Loh P, Sudakov B. The random k‐matching‐free process.
    <i>Random Structures and Algorithms</i>. 2018;53(4):692-716. doi:<a href="https://doi.org/10.1002/rsa.20814">10.1002/rsa.20814</a>
  apa: Krivelevich, M., Kwan, M. A., Loh, P., &#38; Sudakov, B. (2018). The random
    k‐matching‐free process. <i>Random Structures and Algorithms</i>. Wiley. <a href="https://doi.org/10.1002/rsa.20814">https://doi.org/10.1002/rsa.20814</a>
  chicago: Krivelevich, Michael, Matthew Alan Kwan, Po‐Shen Loh, and Benny Sudakov.
    “The Random K‐matching‐free Process.” <i>Random Structures and Algorithms</i>.
    Wiley, 2018. <a href="https://doi.org/10.1002/rsa.20814">https://doi.org/10.1002/rsa.20814</a>.
  ieee: M. Krivelevich, M. A. Kwan, P. Loh, and B. Sudakov, “The random k‐matching‐free
    process,” <i>Random Structures and Algorithms</i>, vol. 53, no. 4. Wiley, pp.
    692–716, 2018.
  ista: Krivelevich M, Kwan MA, Loh P, Sudakov B. 2018. The random k‐matching‐free
    process. Random Structures and Algorithms. 53(4), 692–716.
  mla: Krivelevich, Michael, et al. “The Random K‐matching‐free Process.” <i>Random
    Structures and Algorithms</i>, vol. 53, no. 4, Wiley, 2018, pp. 692–716, doi:<a
    href="https://doi.org/10.1002/rsa.20814">10.1002/rsa.20814</a>.
  short: M. Krivelevich, M.A. Kwan, P. Loh, B. Sudakov, Random Structures and Algorithms
    53 (2018) 692–716.
date_created: 2021-06-18T12:37:40Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-02-23T14:01:07Z
day: '01'
doi: 10.1002/rsa.20814
extern: '1'
external_id:
  arxiv:
  - '1708.01054'
intvolume: '        53'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1708.01054
month: '12'
oa: 1
oa_version: Preprint
page: 692-716
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The random k‐matching‐free process
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 53
year: '2018'
...
---
_id: '9568'
abstract:
- lang: eng
  text: An intercalate in a Latin square is a 2×2 Latin subsquare. Let N be the number
    of intercalates in a uniformly random n×n Latin square. We prove that asymptotically
    almost surely N≥(1−o(1))n2/4, and that EN≤(1+o(1))n2/2 (therefore asymptotically
    almost surely N≤fn2 for any f→∞). This significantly improves the previous best
    lower and upper bounds. We also give an upper tail bound for the number of intercalates
    in two fixed rows of a random Latin square. In addition, we discuss a problem
    of Linial and Luria on low-discrepancy Latin squares.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- 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: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
citation:
  ama: Kwan MA, Sudakov B. Intercalates and discrepancy in random Latin squares. <i>Random
    Structures and Algorithms</i>. 2018;52(2):181-196. doi:<a href="https://doi.org/10.1002/rsa.20742">10.1002/rsa.20742</a>
  apa: Kwan, M. A., &#38; Sudakov, B. (2018). Intercalates and discrepancy in random
    Latin squares. <i>Random Structures and Algorithms</i>. Wiley. <a href="https://doi.org/10.1002/rsa.20742">https://doi.org/10.1002/rsa.20742</a>
  chicago: Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in
    Random Latin Squares.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a
    href="https://doi.org/10.1002/rsa.20742">https://doi.org/10.1002/rsa.20742</a>.
  ieee: M. A. Kwan and B. Sudakov, “Intercalates and discrepancy in random Latin squares,”
    <i>Random Structures and Algorithms</i>, vol. 52, no. 2. Wiley, pp. 181–196, 2018.
  ista: Kwan MA, Sudakov B. 2018. Intercalates and discrepancy in random Latin squares.
    Random Structures and Algorithms. 52(2), 181–196.
  mla: Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random
    Latin Squares.” <i>Random Structures and Algorithms</i>, vol. 52, no. 2, Wiley,
    2018, pp. 181–96, doi:<a href="https://doi.org/10.1002/rsa.20742">10.1002/rsa.20742</a>.
  short: M.A. Kwan, B. Sudakov, Random Structures and Algorithms 52 (2018) 181–196.
date_created: 2021-06-18T12:47:25Z
date_published: 2018-03-01T00:00:00Z
date_updated: 2023-02-23T14:01:09Z
day: '01'
doi: 10.1002/rsa.20742
extern: '1'
external_id:
  arxiv:
  - '1607.04981'
intvolume: '        52'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1607.04981
month: '03'
oa: 1
oa_version: Preprint
page: 181-196
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Intercalates and discrepancy in random Latin squares
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 52
year: '2018'
...
---
_id: '11883'
abstract:
- lang: eng
  text: 'In dynamic graph algorithms the following provide-or-bound problem has to
    be solved quickly: Given a set S containing a subset R and a way of generating
    random elements from S testing for membership in R, either (i) provide an element
    of R, or (ii) give a (small) upper bound on the size of R that holds with high
    probability. We give an optimal algorithm for this problem. This algorithm improves
    the time per operation for various dynamic graph algorithms by a factor of O(log n).
    For example, it improves the time per update for fully dynamic connectivity from
    O(log3n) to O(log2n).'
article_processing_charge: No
article_type: original
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: Mikkel
  full_name: Thorup, Mikkel
  last_name: Thorup
citation:
  ama: 'Henzinger M, Thorup M. Sampling to provide or to bound: With applications
    to fully dynamic graph algorithms. <i>Random Structures and Algorithms</i>. 1997;11(4):369-379.
    doi:<a href="https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x">10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>'
  apa: 'Henzinger, M., &#38; Thorup, M. (1997). Sampling to provide or to bound: With
    applications to fully dynamic graph algorithms. <i>Random Structures and Algorithms</i>.
    Wiley. <a href="https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x">https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>'
  chicago: 'Henzinger, Monika, and Mikkel Thorup. “Sampling to Provide or to Bound:
    With Applications to Fully Dynamic Graph Algorithms.” <i>Random Structures and
    Algorithms</i>. Wiley, 1997. <a href="https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x">https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>.'
  ieee: 'M. Henzinger and M. Thorup, “Sampling to provide or to bound: With applications
    to fully dynamic graph algorithms,” <i>Random Structures and Algorithms</i>, vol.
    11, no. 4. Wiley, pp. 369–379, 1997.'
  ista: 'Henzinger M, Thorup M. 1997. Sampling to provide or to bound: With applications
    to fully dynamic graph algorithms. Random Structures and Algorithms. 11(4), 369–379.'
  mla: 'Henzinger, Monika, and Mikkel Thorup. “Sampling to Provide or to Bound: With
    Applications to Fully Dynamic Graph Algorithms.” <i>Random Structures and Algorithms</i>,
    vol. 11, no. 4, Wiley, 1997, pp. 369–79, doi:<a href="https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x">10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>.'
  short: M. Henzinger, M. Thorup, Random Structures and Algorithms 11 (1997) 369–379.
date_created: 2022-08-17T07:21:55Z
date_published: 1997-12-07T00:00:00Z
date_updated: 2024-11-06T12:00:44Z
day: '07'
doi: 10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x
extern: '1'
intvolume: '        11'
issue: '4'
language:
- iso: eng
month: '12'
oa_version: None
page: 369-379
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Sampling to provide or to bound: With applications to fully dynamic graph
  algorithms'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '1997'
...