Output sensitive fault tolerant maximum matching

DOI10.1007/978-3-031-09574-0_8MaRDI QIDQ2097219zbMATH OpenOpenAlexFDO

Authors Niranka Banerjee, Manoj Gupta, Venkatesh Raman, Saket Saurabh

Publication date 11 November 2022

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

zbMATH Keywords

fault tolerantmaximum matchingupper and lower bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 4k^2 kernel for feedback vertex set
• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Average-case analysis of algorithms for matchings and related problems
• Dual failure resilient BFS structure
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Efficient algorithms for maximum weight matchings in general graphs with small edge weights
• Faster scaling algorithms for general graph matching problems
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Fault Tolerant Approximate BFS Structures
• Fault tolerant reachability for directed graphs
• Fault tolerant spanners for general graphs
• Fault-tolerant spanners
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• Improved purely additive fault-tolerant spanners
• Kernelization. Theory of parameterized preprocessing
• Matching theory
• Multiple source dual fault tolerant BFS trees
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Parameterized algorithms
• Paths, Trees, and Flowers
• Sparse fault-tolerant BFS trees
• Stochastic matching with few queries: (1-ε) approximation
• Stochastic packing integer programs with few queries

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097219)