Cover Image

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liao, Meihao, Pan, Yueyang, Li, Rong-Hua, Wang, Guoren
Format:	Preprint
Published:	2025
Subjects:	Databases Discrete Mathematics Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

Graph Inference with Effective Resistance Queries
by: Bennett, Huck, et al.
Published: (2025)

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

Treewidth Parameterized by Feedback Vertex Number
by: Molter, Hendrik, et al.
Published: (2025)

Exact Causal Attention with 10% Fewer Operations
by: Rybin, Dmitry, et al.
Published: (2025)

Cuts and Gauges for Submodular Width
by: Lanzinger, Matthias
Published: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, 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)

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

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)

Distance-Preserving Graph Compression Techniques
by: Madani, Amirali, et al.
Published: (2023)

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
by: Ganian, Robert, et al.
Published: (2025)

UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
by: Arhire, Andrei, et al.
Published: (2025)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
by: Mathur, Yashaswini, et al.
Published: (2025)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

Total Variation Distance Meets Probabilistic Inference
by: Bhattacharyya, Arnab, et al.
Published: (2023)

Computational Verification of the Buratti--Horak--Rosa Conjecture for Small Integers and Inductive Approaches
by: Naik, Ranjan N
Published: (2025)

Distance Recoloring
by: Banerjee, Niranka, et al.
Published: (2024)

Partial Optimality in the Preordering Problem
by: Stein, David, et al.
Published: (2026)

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
by: Tukan, Murad, et al.
Published: (2024)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
by: Davies, Sami, et al.
Published: (2025)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, et al.
Published: (2025)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
by: Veldt, Nate, et al.
Published: (2025)

Worst-case Error Bounds for Online Learning of Smooth Functions
by: Xie, Weian
Published: (2025)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
by: Chen, Yixin, et al.
Published: (2024)

Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
by: He, Xi
Published: (2025)

Breaking Hard Isomorphism Benchmarks with DRESS
by: Velilla, Eduar Castrillo
Published: (2026)

Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
by: Sharman, Bharat, et al.
Published: (2025)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)

Optimal hypersurface decision trees
by: He, Xi
Published: (2025)

A 4-approximation algorithm for min max correlation clustering
by: Heidrich, Holger, et al.
Published: (2023)

An Exact Solver for Submodular Knapsack Problems
by: Münch, Sabine, et al.
Published: (2025)

Scalable and Provable Kemeny Constant Computation on Static and Dynamic Graphs: A 2-Forest Sampling Approach
by: Li, Cheng, et al.
Published: (2025)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
by: Beisegel, Jesse, et al.
Published: (2025)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

Are Graph Neural Networks Optimal Approximation Algorithms?
by: Yau, Morris, et al.
Published: (2023)

Learning to Prune Instances of Steiner Tree Problem in Graphs
by: Zhang, Jiwei, et al.
Published: (2022)

Isomorphism for Tournaments of Small Twin Width
by: Grohe, Martin, et al.
Published: (2023)