Output sensitive fault tolerant maximum matching

DOI10.1007/978-3-031-09574-0_8OpenAlexW4285149523MaRDI QIDQ2097219

Venkatesh Raman, Saket Saurabh, Manoj Gupta, Niranka Banerjee

Publication date: 11 November 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-09574-0_8

zbMATH Keywords

maximum matchingfault tolerantupper and lower bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Fault tolerant reachability for directed graphs
• Vertex fault tolerant additive spanners
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Dual Failure Resilient BFS Structure
• Sparse Fault-Tolerant BFS Trees
• Fault-tolerant spanners
• Improved Purely Additive Fault-Tolerant Spanners
• Faster scaling algorithms for general graph matching problems
• Average-case analysis of algorithms for matchings and related problems
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Kernelization
• Multiple Source Dual Fault Tolerant BFS Trees
• Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries
• Stochastic matching with few queries: (1-ε) approximation
• Paths, Trees, and Flowers
• Fault Tolerant Approximate BFS Structures
• Fault Tolerant Spanners for General Graphs
• Algorithms – ESA 2004
• Parameterized Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Output sensitive fault tolerant maximum matching