Finding small stabilizers for unstable graphs

DOI10.1007/S10107-014-0854-1zbMATH Open1337.05085OpenAlexW2133509071MaRDI QIDQ896265FDOQ896265

Authors: Adrian Bock, Karthekeyan Chandrasekaran, Jochen Könemann, Britta Peis, Laura Sanità 

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

• Finding small stabilizers for unstable graphs
• Stabilizing weighted graphs
• Additive stabilizers for unstable graphs
• Stabilizing network bargaining games by blocking players
• Stabilizing network bargaining games by blocking players

zbMATH Keywords

game theorymatchingsnetwork bargaining

Mathematics Subject Classification ID

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(\sqrt{\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 (15)

• Simple games versus weighted voting games: bounding the critical threshold value
• Stabilization of capacitated matching games
• Stabilizing Weighted Graphs
• Core stability of vertex cover games
• 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)