Cover Image

Low-Cost Arborescence Under Edge Faults

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dey, Dipan, Kavitha, Telikepalli
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fault-Tolerant Approximate Distance Oracles with a Source Set
by: Dey, Dipan, et al.
Published: (2025)

Perfect Matchings and Popularity in the Many-to-Many Setting
by: Kavitha, Telikepalli, et al.
Published: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Condorcet Dimension and Pareto Optimality for Matchings and Beyond
by: Kavitha, Telikepalli, et al.
Published: (2026)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
by: Mahapatra, Sugyani, et al.
Published: (2021)

Best-of-Both-Worlds Guarantees with Fairer Endings
by: Kavitha, Telikepalli, et al.
Published: (2025)

Rainbow Arborescence Conjecture
by: Bérczi, Kristóf, et al.
Published: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

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

Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
by: Mihalák, Matúš, et al.
Published: (2015)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
by: He, Jialin, et al.
Published: (2025)

Color-Constrained Arborescences in Edge-Colored Digraphs
by: Ardra, P. S., et al.
Published: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
by: Parter, Merav, et al.
Published: (2024)

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
by: Bodwin, Greg, et al.
Published: (2023)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Fault-tolerant $k$-Supplier with Outliers
by: Chakrabarty, Deeparnab, et al.
Published: (2023)

Fault-Equivalent Lowest Common Ancestors
by: Petruschka, Asaf
Published: (2024)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)

Partitioning Trillion Edge Graphs on Edge Devices
by: Chhabra, Adil, et al.
Published: (2024)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
by: Kosinas, Evangelos
Published: (2025)

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
by: Bilò, Davide, et al.
Published: (2024)

An Optimal Sorting Algorithm for Persistent Random Comparison Faults
by: Geissmann, Barbara, et al.
Published: (2025)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Optimal Distributed Replacement Paths
by: Chang, Yi-Jun, et al.
Published: (2025)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
by: Nogler, Jakob, et al.
Published: (2026)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
by: Chekuri, Chandra, et al.
Published: (2024)

Undirected 3-Fault Replacement Path in Nearly Cubic Time
by: Chi, Shucheng, et al.
Published: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
by: Lamprou, Ioannis, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

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

Deterministic Dynamic Edge Colouring
by: Christiansen, Aleksander B. G.
Published: (2024)

Engineering Edge Orientation Algorithms
by: Reinstädtler, H., et al.
Published: (2024)

Edge-weighted Matching in the Dark
by: Huang, Zhiyi, et al.
Published: (2025)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

Buffered Streaming Edge Partitioning
by: Chhabra, Adil, et al.
Published: (2024)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)