Finding small stabilizers for unstable graphs
DOI10.1007/S10107-014-0854-1zbMATH Open1337.05085OpenAlexW2133509071MaRDI QIDQ896265FDOQ896265
Britta Peis, Jochen Könemann, Laura Sanità, Karthekeyan Chandrasekaran, Adrian Bock
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-014-0854-1
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Other game-theoretic models (91A40)
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- The assignment game. I: The core
- The Bargaining Problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The complexity of König subgraph problems and above-guarantee vertex cover
- On the hardness of approximating minimum vertex cover
- Node-and edge-deletion NP-complete problems
- On the power of unique 2-prover 1-round games
- Computational Aspects of Cooperative Game Theory
- Title not available (Why is that?)
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- A characterization of the graphs in which the transversal number equals the matching number
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fractional matchings and the Edmonds-Gallai theorem
- Additive approximation for edge-deletion problems
- Solutions for the stable roommates problem with payments
- Title not available (Why is that?)
- The Cooperative Game Theory Foundations of Network Bargaining Games
- Network bargaining: using approximate blocking sets to stabilize unstable instances
- Integer and Fractional Matchings
- Title not available (Why is that?)
Cited In (14)
- Simple games versus weighted voting games: bounding the critical threshold value
- Stabilization of capacitated matching games
- Stabilizing Weighted Graphs
- A survey of parameterized algorithms and the complexity of edge modification
- The stable fixtures problem with payments
- Graph Stabilization: A Survey
- Title not available (Why is that?)
- The complexity of matching games: a survey
- Minimum cost stability in exchange networks
- Additive stabilizers for unstable graphs
- Stabilizing network bargaining games by blocking players
- Spectral aspects of symmetric matrix signings
- Tractability of König edge deletion problems
- Efficient stabilization of cooperative matching games
This page was built for publication: Finding small stabilizers for unstable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896265)
