Cover Image

Fast Algorithms for Graph Arboricity and Related Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cen, Ruoxu, Fleischmann, Henry, Li, George Z., Li, Jason, Panigrahi, Debmalya
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Network Unreliability in Almost-Linear Time
by: Cen, Ruoxu, et al.
Published: (2025)

Hypergraph Unreliability in Quasi-Polynomial Time
by: Cen, Ruoxu, et al.
Published: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
by: Bhattacharya, Sayan, et al.
Published: (2025)

Improved Directed Expander Decompositions
by: Fleischmann, Henry, et al.
Published: (2025)

Faster Weak Expander Decompositions and Approximate Max Flow
by: Fleischmann, Henry, et al.
Published: (2025)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Learning-Augmented Algorithms for $k$-median via Online Learning
by: Hebbar, Anish, et al.
Published: (2026)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

A Simple and Fast Algorithm for Fair Cuts
by: Li, Jason, et al.
Published: (2024)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Language Generation in the Limit: Noise, Loss, and Feedback
by: Bai, Yannan, et al.
Published: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Reviving Thorup's Shortcut Conjecture
by: Bernstein, Aaron, et al.
Published: (2025)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

Local Sherman's Algorithm for Multi-commodity Flow
by: Li, Jason, et al.
Published: (2025)

Fine-Grained Privacy Guarantees for Coverage Problems
by: Dhulipala, Laxman, et al.
Published: (2024)

Paths and Intersections: Exact Emulators for Planar Graphs
by: Li, George Z., et al.
Published: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
by: Manoharan, Vignesh, et al.
Published: (2025)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
by: Li, Rao
Published: (2024)

A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding
by: Li, Jason, et al.
Published: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
by: Chen, Yong, et al.
Published: (2025)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
by: Murakami, Hitoshi, et al.
Published: (2024)

On Differential Privacy for Adaptively Solving Search Problems via Sketching
by: Feng, Shiyuan, et al.
Published: (2025)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
by: Sun, Ming, et al.
Published: (2022)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search
by: Li, Binhong, et al.
Published: (2025)

SS-GUMAP, SL-GUMAP, SSSL-GUMAP: Fast UMAP Algorithms for Large Graph Drawing
by: Meidiana, Amyra, et al.
Published: (2025)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
by: Casel, Katrin, et al.
Published: (2019)

Improved Algorithms for Effective Resistance Computation on Graphs
by: Yang, Yichun, et al.
Published: (2025)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Algorithms for Halfplane Coverage and Related Problems
by: Wang, Haitao, et al.
Published: (2024)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
by: Assadi, Sepehr, et al.
Published: (2025)