A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs (Englisch)
- Neue Suche nach: Das, Debarati
- Neue Suche nach: Gutenberg, Maximilian Probst
- Neue Suche nach: Nilsen, Christian Wulff
- Neue Suche nach: Das, Debarati
- Neue Suche nach: Gutenberg, Maximilian Probst
- Neue Suche nach: Nilsen, Christian Wulff
In:
ACM-SIAM Symposium on Discrete Algorithms (SODA22) ; Volume 5 of 5
; 3482-3495
;
2022
- Aufsatz (Konferenz) / Print
-
Titel:A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
-
Beteiligte:Das, Debarati ( Autor:in ) / Gutenberg, Maximilian Probst ( Autor:in ) / Nilsen, Christian Wulff ( Autor:in )
-
Kongress:ACM-SIAM Symposium on Discrete Algorithms ; 2022 ; Online
-
Erschienen in:
-
Verlag:
- Neue Suche nach: Curran Associates, Inc.
-
Erscheinungsort:Red Hook, NY
-
Erscheinungsdatum:2022
-
Medientyp:Aufsatz (Konferenz)
-
Format:Print
-
Sprache:Englisch
-
Datenquelle:
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 3043
-
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication TimeChepurko, Nadiia / Clarkson, Kenneth L. / Kacham, Praneeth / Woodruff, David P. et al. | 2022
- 3069
-
Deterministic and Las Vegas Algorithms for Sparse Nonnegative ConvolutionBringmann, Karl / Fischer, Nick / Nakos, Vasileios et al. | 2022
- 3091
-
Simulating Random Walks in Random StreamsKallaugher, John / Kapralov, Michael / Price, Eric et al. | 2022
- 3127
-
Optimal Angle Bounds for Steiner Triangulations of PolygonsBishop, Christopher J. et al. | 2022
- 3144
-
Preprocessing Imprecise Points for the Pareto FrontHoog, Ivor van der / Kostitsyna, Irina / Löffler, Maarten / Speckmann, Bettina et al. | 2022
- 3168
-
Constructing Many Faces in Arrangements of Lines and SegmentsWang, Haitao et al. | 2022
- 3181
-
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle UnionKünnemann, Marvin / Nusser, André et al. | 2022
- 3202
-
An Improved Analysis of Greedy for Online Steiner ForestBamas, Etienne / Drygala, Marina / Maggiori, Andreas et al. | 2022
- 3230
-
Polynomial Integrality Gap of Flow LP for Directed Steiner TreeLi, Shi / Laekhanukit, Bundit et al. | 2022
- 3237
-
Augmenting Edge Connectivity via Isolating CutsCen, Ruoxu / Li, Jason / Panigrahi, Debmalya et al. | 2022
- 3253
-
Local Search for Weighted Tree Augmentation and Steiner TreeTraub, Vera / Zenklusen, Rico et al. | 2022
- 3272
-
Partially Optimal Edge Fault-Tolerant SpannersBodwin, Greg / Dinitz, Michael / Robelle, Caleb et al. | 2022
- 3287
-
Greedy Spanners in Euclidean Spaces Admit Sublinear SeparatorsLe, Hung / Than, Cuong et al. | 2022
- 3311
-
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation ProductLu, Kevin / Williams, Virginia Vassilevska / Wein, Nicole / Xu, Zixuan et al. | 2022
- 3332
-
Near-Optimal Spanners for General Graphs in (Nearly) Linear TimeLe, Hung / Solomon, Shay et al. | 2022
- 3362
-
Co-evolution of Opinion and Social Tie Dynamics Towards Structural BalanceWang, Haotian / Luo, Feng / Gao, Jie et al. | 2022
- 3389
-
Spectral Recovery of Binary Censored Block ModelsDhara, Souvik / Gaudio, Julia / Mossel, Elchanan / Sandon, Colin et al. | 2022
- 3417
-
Fast Consensus via the Unconstrained Undecided State DynamicsBankhamer, Gregor / Berenbrink, Petra / Biermeier, Felix / Elsässer, Robert / Hosseinpour, Hamed / Kaaser, Dominik / Kling, Peter et al. | 2022
- 3430
-
Algorithms Using Local Graph Features to Predict EpidemicsAlimohammadi, Yeganeh / Borgs, Christian / Saberi, Amin et al. | 2022
- 3452
-
Incremental SSSP for Sparse Digraphs Beyond the Hopset BarrierKyng, Rasmus / Meierhans, Simon / Gutenberg, Maximilian Probst et al. | 2022
- 3482
-
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar DigraphsDas, Debarati / Gutenberg, Maximilian Probst / Nilsen, Christian Wulff et al. | 2022
- 3496
-
Dynamic Geometric Set Cover, RevisitedChan, Timothy M. / He, Qizheng / Suri, Subhash / Xue, Jie et al. | 2022
- 3529
-
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCSBehnezhad, Soheil / Khanna, Sanjeev et al. | 2022
- 3567
-
On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius ProblemKlein, Kim-Manuel et al. | 2022
- 3583
-
Optimal Sorting Circuits for Short KeysLin, Wei-Kai / Shi, Elaine et al. | 2022
- 3630
-
Friendly Cut Sparsifiers and Faster Gomory-Hu TreesAbboud, Amir / Krauthgamer, Robert / Trabelsi, Ohad et al. | 2022
- 3650
-
An Improved Algorithm for The k-Dyck Edit Distance ProblemFried, Dvir / Golan, Shay / Kociumaka, Tomasz / Kopelowitz, Tsvi / Porat, Ely / Starikovskaya, Tatiana et al. | 2022
- 3670
-
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy FactorizationBlanca, Antonio / Caputo, Pietro / Chen, Zongchen / Parisi, Daniel / Stefankoviè, Daniel / Vigoda, Eric et al. | 2022
- 3693
-
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral SparsificationChen, Antares / Shi, Jonathan / Trevisan, Luca et al. | 2022
- 3732
-
Scalar and Matrix Chernoff Bounds from .ℓ∞-IndependenceKaufman, Tali / Kyng, Rasmus / Soldá, Federico et al. | 2022
- 3754
-
Compact Redistricting Plans Have Many Spanning TreesProcaccia, Ariel D. / Tucker-Foltz, Jamie et al. | 2022