Finding small stabilizers for unstable graphs

DOI10.1007/s10107-014-0854-1zbMath1337.05085OpenAlexW2133509071MaRDI QIDQ896265

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

zbMATH Keywords

game theorymatchingsnetwork bargaining

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Other game-theoretic models (91A40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (13)

The stable fixtures problem with payments ⋮ Additive stabilizers for unstable graphs ⋮ Stabilization of capacitated matching games ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Simple games versus weighted voting games: bounding the critical threshold value ⋮ Efficient stabilization of cooperative matching games ⋮ Minimum cost stability in exchange networks ⋮ Graph Stabilization: A Survey ⋮ Stabilizing network bargaining games by blocking players ⋮ Stabilizing Weighted Graphs ⋮ Spectral aspects of symmetric matrix signings ⋮ Tractability of König edge deletion problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• The complexity of König subgraph problems and above-guarantee vertex cover
• On the hardness of approximating minimum vertex cover
• Network bargaining: using approximate blocking sets to stabilize unstable instances
• Fractional matchings and the Edmonds-Gallai theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Additive approximation for edge-deletion problems
• Solutions for the stable roommates problem with payments
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• The assignment game. I: The core
• Computational Aspects of Cooperative Game Theory
• The Bargaining Problem
• On the power of unique 2-prover 1-round games
• 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
• The Cooperative Game Theory Foundations of Network Bargaining Games
• Integer and Fractional Matchings
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Node-and edge-deletion NP-complete problems

This page was built for publication: Finding small stabilizers for unstable graphs