Cover Image

Approximate Spanning Tree Counting from Uncorrelated Edge Sets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liu, Yang P., Peng, Richard, Yang, Junzhao
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

Entrywise Approximate Laplacian Solving
by: Chen, Jingbang, et al.
Published: (2024)

Numerical Linear Algebra in Linear Space
by: Liu, Yiping, et al.
Published: (2025)

Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
by: Liu, Yang P., et al.
Published: (2025)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

Budget and Profit Approximations for Spanning Tree Interdiction
by: Ostrovsky, Rafail, et al.
Published: (2025)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
by: Shen, Fangjian, et al.
Published: (2025)

Planar Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2025)

Simple Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2024)

The Cost of Parallelizing Boosting
by: Lyu, Xin, et al.
Published: (2024)

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

Approximate Butterfly Counting in Sublinear Time
by: Luo, Chi, et al.
Published: (2026)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Multi-dimensional Approximate Counting
by: Wang, Dingyu
Published: (2024)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
by: Kolman, Petr
Published: (2024)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
by: Kurita, Kazuhiro, et al.
Published: (2022)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
by: Bilò, Davide, et al.
Published: (2025)

Cover Edge-Based Novel Triangle Counting
by: Bader, David A., et al.
Published: (2024)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
by: Neuwohner, Meike
Published: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
by: Eden, Talya, et al.
Published: (2025)

Approximate Counting for Spin Systems in Sub-Quadratic Time
by: Anand, Konrad, et al.
Published: (2023)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
by: Elkin, Michael, et al.
Published: (2025)

Differentially Private High-Dimensional Approximate Range Counting, Revisited
by: Aumüller, Martin, et al.
Published: (2024)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

Stochastic Minimum Spanning Trees with a Single Sample
by: Hoeksma, Ruben, et al.
Published: (2024)

Two Complexity Results on Spanning-Tree Congestion Problems
by: Atalig, Sunny, et al.
Published: (2026)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
by: Hladík, Richard, et al.
Published: (2024)

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

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

Finding Spanning Trees with Perfect Matchings
by: Bérczi, Kristóf, et al.
Published: (2024)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
by: Ding, Xiangyun, et al.
Published: (2025)

Triangle Counting with Local Edge Differential Privacy
by: Eden, Talya, et al.
Published: (2023)