Buchumschlag

Connectivity Labeling in Faulty Colored Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Petruschka, Asaf, Sapir, Shay, Tzalik, Elad
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
von: Bhanja, Koustav, et al.
Veröffentlicht: (2025)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Fault-Equivalent Lowest Common Ancestors
von: Petruschka, Asaf
Veröffentlicht: (2024)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
von: Parter, Merav, et al.
Veröffentlicht: (2025)

Greedy Completion for Weighted $(α,β)$-Spanners
von: Tzalik, Elad
Veröffentlicht: (2026)

New Oracles and Labeling Schemes for Vertex Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
von: Krauthgamer, Robert, et al.
Veröffentlicht: (2025)

New Greedy Spanners and Applications
von: Popova, Elizaveta, et al.
Veröffentlicht: (2026)

On the Adversarial Robustness of Online Importance Sampling
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Moderate Dimension Reduction for $k$-Center Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2023)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
von: Ferber, Asaf, et al.
Veröffentlicht: (2025)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
von: Roditty, Liam, et al.
Veröffentlicht: (2025)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2025)

Distances in Planar Graphs are Almost for Free!
von: Mozes, Shay, et al.
Veröffentlicht: (2026)

Arboricity-Dependent Algorithms for Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
von: Krauthgamer, Robert, et al.
Veröffentlicht: (2026)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
von: Roditty, Liam, et al.
Veröffentlicht: (2026)

Temporal Graph Reconfiguration for Always-Connected Graphs
von: Sievers, Paul, et al.
Veröffentlicht: (2025)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
von: Long, Yaowei, et al.
Veröffentlicht: (2024)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)

Coloring 3-Colorable Graphs with Low Threshold Rank
von: Hsieh, Jun-Ting
Veröffentlicht: (2025)

Optimal Distance Labeling for Permutation Graphs
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2024)

Exploration of Always $S$-Connected Temporal Graphs
von: Adamson, Duncan, et al.
Veröffentlicht: (2026)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
von: Gao, Jie, et al.
Veröffentlicht: (2025)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Computing the LCP Array of a Labeled Graph
von: Alanko, Jarno, et al.
Veröffentlicht: (2024)

Graph Reconstruction with a Connected Components Oracle
von: Harviainen, Juha, et al.
Veröffentlicht: (2025)

Connectivity-Preserving Minimum Separator in AT-free Graphs
von: Kenig, Batya
Veröffentlicht: (2025)

Graph Traversal via Connected Mobile Agents
von: Jana, Saswata, et al.
Veröffentlicht: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
von: Neiman, Ofer, et al.
Veröffentlicht: (2026)