Cover Image

Scalable and Provable Kemeny Constant Computation on Static and Dynamic Graphs: A 2-Forest Sampling Approach

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Cheng, Liao, Meihao, Li, Rong-Hua, Wang, Guoren
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

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

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
by: Liao, Meihao, et al.
Published: (2025)

BD-Index: Scalable Biharmonic Distance Queries on Large Graphs via Divide-and-Conquer Indexing
by: Pan, Yueyang, et al.
Published: (2025)

Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach
by: Ye, Xiaowei, et al.
Published: (2024)

Scalable $k$-clique Densest Subgraph Search
by: Ye, Xiaowei, et al.
Published: (2024)

Scalable Similarity Search over Large Attributed Bipartite Graphs
by: Ou, Xi, et al.
Published: (2025)

Counting Cohesive Subgraphs with Hereditary Properties
by: Li, Rong-Hua, et al.
Published: (2024)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

A Dynamic Programming Approach to Evader Pathfinding in Static Pursuit Scenarios
by: Samanta, Sukanya, et al.
Published: (2025)

K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential Privacy
by: Sun, Henan, et al.
Published: (2024)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Real-World Graph Analysis: Techniques for Static, Dynamic, and Temporal Communities
by: Rucci, Davide
Published: (2024)

On the Efficient Discovery of Maximum $k$-Defective Biclique
by: Cui, Donghang, et al.
Published: (2025)

Counting Patterns in Degenerate Graphs in Constant Space
by: Komarath, Balagopal, et al.
Published: (2025)

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
by: De Man, Quinten, et al.
Published: (2026)

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

Enumerating m-Length Walks in Directed Graphs with Constant Delay
by: Adamson, Duncan, et al.
Published: (2024)

Influence Maximization in Hypergraphs by Stratified Sampling for Efficient Generation of Reverse Reachable Sets
by: Zhang, Lingling, et al.
Published: (2024)

Provably Fast and Space-Efficient Parallel Biconnectivity
by: Dong, Xiaojun, et al.
Published: (2023)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions
by: Ramos, David Torres, et al.
Published: (2026)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)

CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic Graphs
by: Fan, Zhuochen, et al.
Published: (2024)

Longest Common Extension of a Dynamic String in Parallel Constant Time
by: Albert, Daniel
Published: (2026)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Scalable Multilevel and Memetic Signed Graph Clustering
by: Hausberger, Felix, et al.
Published: (2022)

Efficient Algorithms for Personalized PageRank Computation: A Survey
by: Yang, Mingji, et al.
Published: (2024)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

Efficient space reduction techniques by optimized majority rules for the Kemeny aggregation problem and beyond
by: Phung, Xuan Kien, et al.
Published: (2025)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
by: Ghaffari, Mohsen, et al.
Published: (2026)

Scalable Pattern Matching in Computation Graphs
by: Mondada, Luca, et al.
Published: (2024)

SVD Provably Denoises Nearest Neighbor Data
by: Kannan, Ravindran, et al.
Published: (2026)

Constant sensitivity on the CDAWGs
by: Hamai, Rikuya, et al.
Published: (2025)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Revisiting Local Computation of PageRank: Simple and Optimal
by: Wang, Hanzhi, et al.
Published: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Computing k-mers in Graphs
by: Alanko, Jarno N., et al.
Published: (2025)

Efficient Computation of Periods and Covers Using Sampling
by: Lecroq, Thierry, et al.
Published: (2024)