Faster algorithms for security games on matroids
From MaRDI portal
Publication:666676
DOI10.1007/s00453-018-0466-xzbMath1422.91035OpenAlexW2809373373WikidataQ115149029 ScholiaQ115149029MaRDI QIDQ666676
Francisco Barahona, Mourad Baïou
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0466-x
Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Noncooperative games (91A10) 2-person games (91A05)
Related Items
Hitting a path: a generalization of weighted connectivity via game theory, New polyhedral and algorithmic results on greedoids
Cites Work
- Security games on matroids
- A faster strongly polynomial time algorithm for submodular function minimization
- Testing membership in matroid polyhedra
- The ellipsoid method and its consequences in combinatorial optimization
- Separating from the dominant of the spanning tree polytope
- Packing algorithms for arborescences (and spanning trees) in capacitated graphs
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- A rounding technique for the polymatroid membership problem
- A class of inverse dominant problems under weighted \(l_{\infty }\) norm and an improved complexity bound for Radzik's algorithm
- Design of Network Topology in an Adversarial Environment
- On the Problem of Decomposing a Graph into n Connected Factors
- Edge-Disjoint Spanning Trees of Finite Graphs
- A new approach to the maximum-flow problem
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- Packing Spanning Trees
- On Nonlinear Fractional Programming
- Matroids and the greedy algorithm
- Unnamed Item
- Unnamed Item
