How to Secure Matchings against Edge Failures
From MaRDI portal
Publication:5157391
DOI10.1137/20M1336229OpenAlexW3204948599MaRDI QIDQ5157391
Felix Hommelsheim, Moritz Mühlenthaler, Oliver Schaudt
Publication date: 18 October 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.01299
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- On the NP-completeness of the perfect matching free subgraph problem
- An \(s\)-\(t\) connection problem with adaptability
- Approximation algorithms for spanner problems and directed Steiner forest
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Bulk-robust combinatorial optimization
- Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Set connectivity problems in undirected graphs and the directed steiner network problem
- Coverings of Bipartite Graphs
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Polylogarithmic inapproximability
- Totally-Balanced and Greedy Matrices
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmentation Problems
- Robust Assignments via Ear Decompositions and Randomized Rounding
- Making Bipartite Graphs DM-Irreducible
- Robust recoverable perfect matchings
- How to Secure Matchings Against Edge Failures
- Analytical approach to parallel repetition
- Matching preclusion for some interconnection networks
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: How to Secure Matchings against Edge Failures
