---
OA_place: publisher
OA_type: gold
_id: '22246'
abstract:
- lang: eng
text: "In this paper we construct distance sketches for intersection graphs of arbitrary
path-connected regions in the plane (known as the string graphs) in the constant
and 1+ε distortion regimes. Furthermore, the distance sketches themselves are
planar graphs. First, we show that every unweighted string graph G has an O(1)-distortion
planar emulator: that is, there exists an edge-weighted planar graph H containing
every vertex in G, such that every pair of vertices (u,v) satisfies δG(u,v) ≤
δH(u,v) ≤ O(1) · δG(u,v). Furthermore, we show that for any constant ε > 0, there
is an edge-weighted planar graph H′ such that every pair of vertices (u,v) satisfies
δG(u,v) ≤ δH′(u,v) ≤ (1+ε) · δG(u,v) + O(ε−4polylogn). No previous constructions
of sparse distance sketches were known even for intersection graphs of simple
shapes like axis-parallel rectangles or fat convex polygons.\r\nAs applications,
we construct the first (1+ε, +O(1)) mixed-distortion tree cover and distance oracle
for arbitrary string graphs, as well as the first additive +(εΔ+O(1))-distortion
embedding of string graphs G with diameter Δ into graphs of constant treewidth
O(ε−4)."
acknowledgement: "Hsien-Chih Chang and Jonathan Conroy are supported by the U.S.\r\nNational
Science Foundation CAREER Award under the Grant No.\r\nCCF-2443017."
article_processing_charge: No
arxiv: 1
author:
- first_name: Hsien Chih
full_name: Chang, Hsien Chih
last_name: Chang
- first_name: Jonathan
full_name: Conroy, Jonathan
last_name: Conroy
- first_name: Zihan
full_name: Tan, Zihan
last_name: Tan
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Chang HC, Conroy J, Tan Z, Zheng DW. Cutting planarians: Planar emulators
for string graphs. In: 58th Annual ACM Symposium on Theory of Computing.
Association for Computing Machinery; 2026:2140-2151. doi:10.1145/3798129.3800917'
apa: 'Chang, H. C., Conroy, J., Tan, Z., & Zheng, D. W. (2026). Cutting planarians:
Planar emulators for string graphs. In 58th Annual ACM Symposium on Theory
of Computing (pp. 2140–2151). Salt Lake City, UT, United States: Association
for Computing Machinery. https://doi.org/10.1145/3798129.3800917'
chicago: 'Chang, Hsien Chih, Jonathan Conroy, Zihan Tan, and Da Wei Zheng. “Cutting
Planarians: Planar Emulators for String Graphs.” In 58th Annual ACM Symposium
on Theory of Computing, 2140–51. Association for Computing Machinery, 2026.
https://doi.org/10.1145/3798129.3800917.'
ieee: 'H. C. Chang, J. Conroy, Z. Tan, and D. W. Zheng, “Cutting planarians: Planar
emulators for string graphs,” in 58th Annual ACM Symposium on Theory of Computing,
Salt Lake City, UT, United States, 2026, pp. 2140–2151.'
ista: 'Chang HC, Conroy J, Tan Z, Zheng DW. 2026. Cutting planarians: Planar emulators
for string graphs. 58th Annual ACM Symposium on Theory of Computing. STOC: Symposium
on the Theory of Computing, 2140–2151.'
mla: 'Chang, Hsien Chih, et al. “Cutting Planarians: Planar Emulators for String
Graphs.” 58th Annual ACM Symposium on Theory of Computing, Association
for Computing Machinery, 2026, pp. 2140–51, doi:10.1145/3798129.3800917.'
short: H.C. Chang, J. Conroy, Z. Tan, D.W. Zheng, in:, 58th Annual ACM Symposium
on Theory of Computing, Association for Computing Machinery, 2026, pp. 2140–2151.
conference:
end_date: 2026-06-26
location: Salt Lake City, UT, United States
name: 'STOC: Symposium on the Theory of Computing'
start_date: 2026-06-22
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-05T22:01:37Z
date_published: 2026-06-09T00:00:00Z
date_updated: 2026-07-06T10:25:23Z
day: '09'
ddc:
- '500'
- '000'
department:
- _id: MoHe
doi: 10.1145/3798129.3800917
external_id:
arxiv:
- '2510.21700'
file:
- access_level: open_access
checksum: c184596a3e18fee912caef4c7751a96d
content_type: application/pdf
creator: dernst
date_created: 2026-07-06T10:23:09Z
date_updated: 2026-07-06T10:23:09Z
file_id: '22253'
file_name: 2026_STOC_Chang.pdf
file_size: 2015699
relation: main_file
success: 1
file_date_updated: 2026-07-06T10:23:09Z
fulldoi: https://doi.org/10.1145/3798129.3800917
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2140-2151
publication: 58th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400725364'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Cutting planarians: Planar emulators for string graphs'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22245'
abstract:
- lang: eng
text: "A single-commodity congestion approximator for a graph is a compact data
structure that approximately predicts the edge congestion required to route any
set of single-commodity flow demands in a network. A hierarchical congestion approximator
(HCA) consists of a laminar family of cuts in the graph and has numerous applications
in approximating cut and flow problems in graphs, designing efficient routing
schemes, and managing distributed networks.\r\nThere is a tradeoff between the
running time for computing an HCA and its approximation quality. The best polynomial-time
construction in an n-node graph gives an HCA with approximation quality O(log1.5n
loglogn). Among near-linear time algorithms, the best previous result achieves
approximation quality O(log4 n). We improve upon the latter result by giving the
first near-linear time algorithm for computing an HCA with approximation quality
O(log2 n loglogn). Additionally, our algorithm can be implemented in the parallel
setting with polylogarithmic span and near-linear work, achieving the same approximation
quality. This improves upon the best previous such algorithm, which has an O(log9n)
approximation quality. We also present a lower bound of Ω(logn) for the approximation
guarantee of hierarchical congestion approximators.\r\nCrucial for achieving a
near-linear running time is a new partitioning routine that, unlike previous such
routines, manages to avoid recursing on large subgraphs. To achieve the improved
approximation quality, we introduce the new concept of border routability of a
cut and provide an improved sparsest cut oracle for general vertex weights."
acknowledgement: "We thank Evangelos Kosinas for helpful discussions on this topic.\r\nFunded
by the European Union. Views and opinions expressed\r\nare however those of the
author(s) only and do not necessarily\r\nreflect those of the European Union or
the European Research\r\nCouncil Executive Agency. Neither the European Union nor
the\r\ngranting authority can be held responsible for them.\r\nThis project has
received funding from the European Research\r\nCouncil (ERC) under the European
Union’s Horizon 2020 research\r\nand innovation programme (MoDynStruct, No. 101019564)\r\nand
the Austrian Science Fund (FWF) grant DOI 10.55776/I5982. For\r\nopen access purposes,
the author has applied a CC BY public copyright license to any author-accepted manuscript
version arising\r\nfrom this submission.\r\nThis project has received funding from
the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858."
article_processing_charge: Yes
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: Robin
full_name: Münk, Robin
last_name: Münk
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
citation:
ama: 'Henzinger M, Münk R, Räcke H. An improved quality hierarchical congestion
approximator in near-linear time. In: 58th Annual ACM Symposium on Theory of
Computing. ACM; 2026:1417-1428. doi:10.1145/3798129.3800851'
apa: 'Henzinger, M., Münk, R., & Räcke, H. (2026). An improved quality hierarchical
congestion approximator in near-linear time. In 58th Annual ACM Symposium on
Theory of Computing (pp. 1417–1428). Salt Lake City, UT, United States: ACM.
https://doi.org/10.1145/3798129.3800851'
chicago: Henzinger, Monika, Robin Münk, and Harald Räcke. “An Improved Quality Hierarchical
Congestion Approximator in Near-Linear Time.” In 58th Annual ACM Symposium
on Theory of Computing, 1417–28. ACM, 2026. https://doi.org/10.1145/3798129.3800851.
ieee: M. Henzinger, R. Münk, and H. Räcke, “An improved quality hierarchical congestion
approximator in near-linear time,” in 58th Annual ACM Symposium on Theory of
Computing, Salt Lake City, UT, United States, 2026, pp. 1417–1428.
ista: 'Henzinger M, Münk R, Räcke H. 2026. An improved quality hierarchical congestion
approximator in near-linear time. 58th Annual ACM Symposium on Theory of Computing.
STOC: Symposium on the Theory of Computing, 1417–1428.'
mla: Henzinger, Monika, et al. “An Improved Quality Hierarchical Congestion Approximator
in Near-Linear Time.” 58th Annual ACM Symposium on Theory of Computing,
ACM, 2026, pp. 1417–28, doi:10.1145/3798129.3800851.
short: M. Henzinger, R. Münk, H. Räcke, in:, 58th Annual ACM Symposium on Theory
of Computing, ACM, 2026, pp. 1417–1428.
conference:
end_date: 2026-06-26
location: Salt Lake City, UT, United States
name: 'STOC: Symposium on the Theory of Computing'
start_date: 2026-06-22
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-05T22:01:36Z
date_published: 2026-06-09T00:00:00Z
date_updated: 2026-09-17T12:39:36Z
day: '09'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3798129.3800851
ec_funded: 1
external_id:
arxiv:
- '2511.03716'
file:
- access_level: open_access
checksum: 2bef46be8da6d19a641697bb0d8ade65
content_type: application/pdf
creator: dernst
date_created: 2026-07-06T06:57:16Z
date_updated: 2026-07-06T06:57:16Z
file_id: '22250'
file_name: 2026_STOC_HenzingerMo.pdf
file_size: 919005
relation: main_file
success: 1
file_date_updated: 2026-07-06T06:57:16Z
fulldoi: https://doi.org/10.1145/3798129.3800851
has_accepted_license: '1'
keyword:
- Congestion Approximators
- Hierarchical Graph Decompositions
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1417-1428
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 58th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400725364'
issn:
- 0737-8017
publication_status: published
publisher: ACM
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: An improved quality hierarchical congestion approximator in near-linear time
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20007'
abstract:
- lang: eng
text: 'There is no known polynomial-time algorithm for graph isomorphism testing,
but elementary combinatorial “refinement” algorithms seem to be very efficient
in practice. Some philosophical justification for this phenomenon is provided
by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time
combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex
classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”)
yields a so-called canonical labelling scheme for “almost all graphs”. More precisely,
for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm
assigns labels to vertices in a way that easily permits isomorphism-testing against
any other graph.'
acknowledgement: All authors were supported by ERC Starting Grant “RANDSTRUCT” No.
101076777. Michael Anastos was also supported in part by the Austrian Science Fund
(FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.
For Open Access purposes, the authors have applied a CC BY public copyright license
to any author accepted manuscript version arising from this submission.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- 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: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
citation:
ama: 'Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In:
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association
for Computing Machinery; 2025:2098-2106. doi:10.1145/3717823.3718173'
apa: 'Anastos, M., Kwan, M. A., & Moore, B. (2025). Smoothed analysis for graph
isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing
(pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718173'
chicago: Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis
for Graph Isomorphism.” In Proceedings of the 57th Annual ACM Symposium on
Theory of Computing, 2098–2106. Association for Computing Machinery, 2025.
https://doi.org/10.1145/3717823.3718173.
ieee: M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,”
in Proceedings of the 57th Annual ACM Symposium on Theory of Computing,
Prague, Czechia, 2025, pp. 2098–2106.
ista: 'Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism.
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium
on Theory of Computing, 2098–2106.'
mla: Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 2098–106, doi:10.1145/3717823.3718173.
short: M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp.
2098–2106.
conference:
end_date: 2025-06-27
location: Prague, Czechia
name: 'STOC: Symposium on Theory of Computing'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2025-07-14T06:33:50Z
day: '15'
ddc:
- '000'
department:
- _id: MaKw
doi: 10.1145/3717823.3718173
ec_funded: 1
external_id:
arxiv:
- '2410.06095'
file:
- access_level: open_access
checksum: cf0ab9cb9c6abda188de13dc3f9a4c9b
content_type: application/pdf
creator: dernst
date_created: 2025-07-14T06:13:10Z
date_updated: 2025-07-14T06:13:10Z
file_id: '20012'
file_name: 2025_STOC_Anastos.pdf
file_size: 706445
relation: main_file
success: 1
file_date_updated: 2025-07-14T06:13:10Z
fulldoi: https://doi.org/10.1145/3717823.3718173
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2098-2106
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400715105'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Smoothed analysis for graph isomorphism
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20008'
abstract:
- lang: eng
text: 'We study the complexity of a class of promise graph homomorphism problems.
For a fixed graph H, the H-colouring problem is to decide whether a given graph
has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard
for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018]
conjectured the hardness extends to promise graph homomorphism problems as follows:
fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism
from G to H, it is NP-hard to distinguish between graphs that are G-colourable
and those that are not H-colourable. We confirm this conjecture in the cases when
both G and H are 4-colourable. This is a common generalisation of previous results
of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and
Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach
to promise constraint satisfaction with methods of topological combinatorics and
equivariant obstruction theory.'
acknowledgement: This research was supported by the Austrian Science Fund (FWF project
P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed
by the Ministry of Education, Youth and Sports of the Czech Republic. This project
has also received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
orcid: 0000-0002-7840-5062
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Jakub
full_name: Opršal, Jakub
id: ec596741-c539-11ec-b829-c79322a91242
last_name: Opršal
orcid: 0000-0003-1245-3456
- first_name: Gianluca
full_name: Tasinato, Gianluca
id: 0433290C-AF8F-11E9-A4C7-F729E6697425
last_name: Tasinato
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring
G-colourable graphs. In: Proceedings of the 57th Annual ACM Symposium on Theory
of Computing. Association for Computing Machinery; 2025:72-83. doi:10.1145/3717823.3718154'
apa: 'Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U.
(2025). Hardness of 4-colouring G-colourable graphs. In Proceedings of the
57th Annual ACM Symposium on Theory of Computing (pp. 72–83). Prague, Czechia:
Association for Computing Machinery. https://doi.org/10.1145/3717823.3718154'
chicago: Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and
Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In Proceedings of
the 57th Annual ACM Symposium on Theory of Computing, 72–83. Association for
Computing Machinery, 2025. https://doi.org/10.1145/3717823.3718154.
ieee: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of 4-colouring G-colourable graphs,” in Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, Prague, Czechia, 2025, pp. 72–83.
ista: 'Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness
of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium
on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.'
mla: Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 72–83, doi:10.1145/3717823.3718154.
short: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 72–83.
conference:
end_date: 2025-06-27
location: Prague, Czechia
name: 'STOC: Symposium on Theory of Computing'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2026-07-29T13:13:17Z
day: '15'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1145/3717823.3718154
ec_funded: 1
file:
- access_level: open_access
checksum: 2c9ae7ad0102c41124976f4cb5182760
content_type: application/pdf
creator: dernst
date_created: 2025-07-14T06:42:58Z
date_updated: 2025-07-14T06:42:58Z
file_id: '20013'
file_name: 2025_STOC_Avvakumov.pdf
file_size: 940827
relation: main_file
success: 1
file_date_updated: 2025-07-14T06:42:58Z
fulldoi: https://doi.org/10.1145/3717823.3718154
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 72-83
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400715105'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '20339'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Hardness of 4-colouring G-colourable graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
_id: '11865'
abstract:
- lang: eng
text: We present the first sublinear-time algorithm that can compute the edge connectivity
λ of a network exactly on distributed message-passing networks (the CONGEST model),
as long as the network contains no multi-edge. We present the first sublinear-time
algorithm for a distributed message-passing network sto compute its edge connectivity
λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm
takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ
with high probability, where n and D are the number of nodes and the diameter
of the network, respectively, and Õ hides polylogarithmic factors. This running
time is sublinear in n (i.e. Õ(n1−є)) whenever D is. Previous sublinear-time distributed
algorithms can solve this problem either (i) exactly only when λ=O(n1/8−є) [Thurimella
PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14]
or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve
this we develop and combine several new techniques. First, we design the first
distributed algorithm that can compute a k-edge connectivity certificate for any
k=O(n1−є) in time Õ(√nk+D). The previous sublinear-time algorithm can do so only
when k=o(√n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the
first parallel algorithm with polylogarithmic depth and near-linear work. Previous
near-linear work algorithms are essentially sequential and previous polylogarithmic-depth
algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]).
Second, we show that by combining the recent distributed expander decomposition
technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential
deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15],
we can decompose the network into a sublinear number of clusters with small average
diameter and without any mincut separating a cluster (except the “trivial” ones).
This leads to a simplification of the Kawarabayashi-Thorup framework (except that
we are randomized while they are deterministic). This might make this framework
more useful in other models of computation. Finally, by extending the tree packing
technique from [Karger STOC’96], we can find the minimum cut in time proportional
to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time
algorithm for computing exact minimum cut for weighted graphs.
article_processing_charge: No
arxiv: 1
author:
- first_name: Mohit
full_name: Daga, Mohit
last_name: Daga
- 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: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
- first_name: Thatchaphol
full_name: Saranurak, Thatchaphol
last_name: Saranurak
citation:
ama: 'Daga M, Henzinger M, Nanongkai D, Saranurak T. Distributed edge connectivity
in sublinear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing. Association for Computing Machinery; 2019:343–354.
doi:10.1145/3313276.3316346'
apa: 'Daga, M., Henzinger, M., Nanongkai, D., & Saranurak, T. (2019). Distributed
edge connectivity in sublinear time. In Proceedings of the 51st Annual ACM
SIGACT Symposium on Theory of Computing (pp. 343–354). Phoenix, AZ, United
States: Association for Computing Machinery. https://doi.org/10.1145/3313276.3316346'
chicago: Daga, Mohit, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak.
“Distributed Edge Connectivity in Sublinear Time.” In Proceedings of the 51st
Annual ACM SIGACT Symposium on Theory of Computing, 343–354. Association for
Computing Machinery, 2019. https://doi.org/10.1145/3313276.3316346.
ieee: M. Daga, M. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge connectivity
in sublinear time,” in Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 343–354.
ista: 'Daga M, Henzinger M, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity
in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing. STOC: Symposium on Theory of Computing, 343–354.'
mla: Daga, Mohit, et al. “Distributed Edge Connectivity in Sublinear Time.” Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association
for Computing Machinery, 2019, pp. 343–354, doi:10.1145/3313276.3316346.
short: M. Daga, M. Henzinger, D. Nanongkai, T. Saranurak, in:, Proceedings of the
51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing
Machinery, 2019, pp. 343–354.
conference:
end_date: 2019-06-26
location: Phoenix, AZ, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2019-06-23
date_created: 2022-08-16T09:11:17Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2024-11-06T12:19:15Z
day: '01'
doi: 10.1145/3313276.3316346
extern: '1'
external_id:
arxiv:
- '1904.04341'
fulldoi: https://doi.org/10.1145/3313276.3316346
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1904.04341
month: '06'
oa: 1
oa_version: Preprint
page: 343–354
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-1-4503-6705-9
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Distributed edge connectivity in sublinear time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '11866'
abstract:
- lang: eng
text: "We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time
algorithm for solving the single-source shortest paths problem on distributed
weighted networks (the CONGEST model); here n is the number of nodes in the network
and D is its (hop) diameter. This is the first non-trivial deterministic algorithm
for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation
Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large
as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s
Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running
time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al.
STOC 2011] modulo some lower-order terms, thus essentially settling the status
of this problem which was raised at least a decade ago [Elkin SIGACT News 2004].
It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for
approximating a network’s weighted diameter which almost matches the lower bound
by Holzer et al. [PODC 2012].\r\n\r\nIn achieving this result, we develop two
techniques which might be of independent interest and useful in other settings:
(i) a deterministic process that replaces the “hitting set argument” commonly
used for shortest paths computation in various settings, and (ii) a simple, deterministic,
construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these
techniques with many distributed algorithmic techniques, some of which from problems
that are not directly related to shortest paths, e.g. ruling sets [Goldberg et
al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance
estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads
to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation
O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation
O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights
are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC
2014]. The second result partially answers an open problem raised by McGregor
in 2006 [sublinear.info
, Problem 14]."
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. A deterministic almost-tight distributed
algorithm for approximating single-source shortest paths. In: 48th Annual ACM
SIGACT Symposium on Theory of Computing. Association for Computing Machinery;
2016:489-498. doi:10.1145/2897518.2897638'
apa: 'Henzinger, M., Krinninger, S., & Nanongkai, D. (2016). A deterministic
almost-tight distributed algorithm for approximating single-source shortest paths.
In 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 489–498).
Cambridge, MA, United States: Association for Computing Machinery. https://doi.org/10.1145/2897518.2897638'
chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic
Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.”
In 48th Annual ACM SIGACT Symposium on Theory of Computing, 489–98. Association
for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897638.
ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight
distributed algorithm for approximating single-source shortest paths,” in 48th
Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United
States, 2016, pp. 489–498.
ista: 'Henzinger M, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight
distributed algorithm for approximating single-source shortest paths. 48th Annual
ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing,
489–498.'
mla: Henzinger, Monika, et al. “A Deterministic Almost-Tight Distributed Algorithm
for Approximating Single-Source Shortest Paths.” 48th Annual ACM SIGACT Symposium
on Theory of Computing, Association for Computing Machinery, 2016, pp. 489–98,
doi:10.1145/2897518.2897638.
short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium
on Theory of Computing, Association for Computing Machinery, 2016, pp. 489–498.
conference:
end_date: 2016-06-21
location: Cambridge, MA, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2016-06-19
date_created: 2022-08-16T09:19:31Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2024-11-06T12:19:26Z
day: '01'
doi: 10.1145/2897518.2897638
extern: '1'
external_id:
arxiv:
- '1504.07056'
fulldoi: https://doi.org/10.1145/2897518.2897638
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.07056
month: '06'
oa: 1
oa_version: Preprint
page: 489 - 498
publication: 48th Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-145034132-5
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deterministic almost-tight distributed algorithm for approximating single-source
shortest paths
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '11867'
abstract:
- lang: eng
text: We present two deterministic dynamic algorithms for the maximum matching problem.
(1) An algorithm that maintains a (2+є)-approximate maximum matching in general
graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an
αK approximation of the value of the maximum matching with O(n2/K) update time
in bipartite graphs, for every sufficiently large constant positive integer K.
Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the
first deterministic algorithm that can maintain an o(logn)-approximate maximum
matching with polylogarithmic update time, improving the seminal result of Onak
et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of
the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS
2011]. Result (2) achieves a better-than-two approximation with arbitrarily small
polynomial update time on bipartite graphs. Previously the best update time for
this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current
number of edges in the graph.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- 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: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Bhattacharya S, Henzinger M, Nanongkai D. New deterministic approximation
algorithms for fully dynamic matching. In: 48th Annual ACM SIGACT Symposium
on Theory of Computing. Association for Computing Machinery; 2016:398-411.
doi:10.1145/2897518.2897568'
apa: 'Bhattacharya, S., Henzinger, M., & Nanongkai, D. (2016). New deterministic
approximation algorithms for fully dynamic matching. In 48th Annual ACM SIGACT
Symposium on Theory of Computing (pp. 398–411). Cambridge, MA, United States:
Association for Computing Machinery. https://doi.org/10.1145/2897518.2897568'
chicago: Bhattacharya, Sayan, Monika Henzinger, and Danupon Nanongkai. “New Deterministic
Approximation Algorithms for Fully Dynamic Matching.” In 48th Annual ACM SIGACT
Symposium on Theory of Computing, 398–411. Association for Computing Machinery,
2016. https://doi.org/10.1145/2897518.2897568.
ieee: S. Bhattacharya, M. Henzinger, and D. Nanongkai, “New deterministic approximation
algorithms for fully dynamic matching,” in 48th Annual ACM SIGACT Symposium
on Theory of Computing, Cambridge, MA, United States, 2016, pp. 398–411.
ista: 'Bhattacharya S, Henzinger M, Nanongkai D. 2016. New deterministic approximation
algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory
of Computing. STOC: Symposium on Theory of Computing, 398–411.'
mla: Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for
Fully Dynamic Matching.” 48th Annual ACM SIGACT Symposium on Theory of Computing,
Association for Computing Machinery, 2016, pp. 398–411, doi:10.1145/2897518.2897568.
short: S. Bhattacharya, M. Henzinger, D. Nanongkai, in:, 48th Annual ACM SIGACT
Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp.
398–411.
conference:
end_date: 2016-06-21
location: Cambridge, MA, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2016-06-19
date_created: 2022-08-16T09:27:35Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2024-11-06T12:19:37Z
day: '01'
doi: 10.1145/2897518.2897568
extern: '1'
external_id:
arxiv:
- '1604.05765'
fulldoi: https://doi.org/10.1145/2897518.2897568
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.05765
month: '06'
oa: 1
oa_version: Preprint
page: 398 - 411
publication: 48th Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-145034132-5
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: New deterministic approximation algorithms for fully dynamic matching
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '11869'
abstract:
- lang: eng
text: "While in many graph mining applications it is crucial to handle a stream
of updates efficiently in terms of both time and space, not much was known about
achieving such type of algorithm. In this paper we study this issue for a problem
which lies at the core of many graph mining applications called densest subgraph
problem. We develop an algorithm that achieves time- and space-efficiency for
this problem simultaneously. It is one of the first of its kind for graph problems
to the best of our knowledge.\r\n\r\nGiven an input graph, the densest subgraph
is the subgraph that maximizes the ratio between the number of edges and the number
of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate
solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized
time per update; here, $n$ is the number of nodes in the graph and ~O hides the
O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with
more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm
and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm
that can maintain the densest subgraph in one pass. Prior to this, no algorithm
could do so even in the special case of an incremental stream and even when there
is no time restriction. The previously best algorithm in this setting required
O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up
to a polylogarithmic factor."
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- 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: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
- first_name: Charalampos
full_name: Tsourakakis, Charalampos
last_name: Tsourakakis
citation:
ama: 'Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. Space- and time-efficient
algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: 47th
Annual ACM Symposium on Theory of Computing. Association for Computing Machinery;
2015:173-182. doi:10.1145/2746539.2746592'
apa: 'Bhattacharya, S., Henzinger, M., Nanongkai, D., & Tsourakakis, C. (2015).
Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass
dynamic streams. In 47th Annual ACM Symposium on Theory of Computing (pp.
173–182). Portland, OR, United States: Association for Computing Machinery. https://doi.org/10.1145/2746539.2746592'
chicago: Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Charalampos
Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs
on One-Pass Dynamic Streams.” In 47th Annual ACM Symposium on Theory of Computing,
173–82. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746592.
ieee: S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and
time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,”
in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United
States, 2015, pp. 173–182.
ista: 'Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. 2015. Space- and
time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams.
47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of
Computing, 173–182.'
mla: Bhattacharya, Sayan, et al. “Space- and Time-Efficient Algorithm for Maintaining
Dense Subgraphs on One-Pass Dynamic Streams.” 47th Annual ACM Symposium on
Theory of Computing, Association for Computing Machinery, 2015, pp. 173–82,
doi:10.1145/2746539.2746592.
short: S. Bhattacharya, M. Henzinger, D. Nanongkai, C. Tsourakakis, in:, 47th Annual
ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015,
pp. 173–182.
conference:
end_date: 2015-06-17
location: Portland, OR, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2015-06-14
date_created: 2022-08-16T09:36:48Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2024-11-06T12:20:01Z
day: '01'
doi: 10.1145/2746539.2746592
extern: '1'
external_id:
arxiv:
- '1504.02268'
fulldoi: https://doi.org/10.1145/2746539.2746592
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.02268
month: '06'
oa: 1
oa_version: Preprint
page: 173 - 182
publication: 47th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-145033536-2
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass
dynamic streams
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '11870'
abstract:
- lang: eng
text: "We consider dynamic algorithms for maintaining Single-Source Reachability
(SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed
graphs under edge deletions (decremental algorithms). The previous fastest algorithm
for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it
has O(1) query time and O(mn) total update time (i.e., linear amortized update
time if all edges are deleted). This algorithm serves as a building block for
several other dynamic algorithms. The question whether its total update time can
be improved is a major, long standing, open problem.\r\n\r\nIn this paper, we
answer this question affirmatively. We obtain a randomized algorithm which, in
a simplified form, achieves an Õ(mn0.984) expected total update time for SSR and
(1 + ε)-approximate SSSP, where Õ(·) hides poly log n. We also extend our algorithm
to achieve roughly the same running time for Strongly Connected Components (SCC),
improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that
improves the Õ (mn log W)-time algorithm of Bernstein (STOC 2013) for approximating
SSSP on weighted directed graphs, where the edge weights are integers from 1 to
W. All our algorithms have constant query time in the worst case."
article_number: 674 - 683
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. Sublinear-time decremental algorithms
for single-source reachability and shortest paths on directed graphs. In: 46th
Annual ACM Symposium on Theory of Computing. Association for Computing Machinery;
2014. doi:10.1145/2591796.2591869'
apa: 'Henzinger, M., Krinninger, S., & Nanongkai, D. (2014). Sublinear-time
decremental algorithms for single-source reachability and shortest paths on directed
graphs. In 46th Annual ACM Symposium on Theory of Computing. New York,
NY, United States: Association for Computing Machinery. https://doi.org/10.1145/2591796.2591869'
chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed
Graphs.” In 46th Annual ACM Symposium on Theory of Computing. Association
for Computing Machinery, 2014. https://doi.org/10.1145/2591796.2591869.
ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time decremental
algorithms for single-source reachability and shortest paths on directed graphs,”
in 46th Annual ACM Symposium on Theory of Computing, New York, NY, United
States, 2014.
ista: 'Henzinger M, Krinninger S, Nanongkai D. 2014. Sublinear-time decremental
algorithms for single-source reachability and shortest paths on directed graphs.
46th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of
Computing, 674–683.'
mla: Henzinger, Monika, et al. “Sublinear-Time Decremental Algorithms for Single-Source
Reachability and Shortest Paths on Directed Graphs.” 46th Annual ACM Symposium
on Theory of Computing, 674–683, Association for Computing Machinery, 2014,
doi:10.1145/2591796.2591869.
short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 46th Annual ACM Symposium
on Theory of Computing, Association for Computing Machinery, 2014.
conference:
end_date: 2014-06-03
location: New York, NY, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2014-05-31
date_created: 2022-08-16T09:41:57Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2024-11-06T12:20:12Z
day: '01'
doi: 10.1145/2591796.2591869
extern: '1'
external_id:
arxiv:
- '1504.07959'
fulldoi: https://doi.org/10.1145/2591796.2591869
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.07959
month: '05'
oa: 1
oa_version: Preprint
publication: 46th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- 978-145032710-7
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sublinear-time decremental algorithms for single-source reachability and shortest
paths on directed graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...