Finding small stabilizers for unstable graphs

DOI10.1007/S10107-014-0854-1MaRDI QIDQ896265zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

game theorymatchingsnetwork bargaining

Mathematics Subject Classification ID

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

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

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• A characterization of the graphs in which the transversal number equals the matching number
• Additive approximation for edge-deletion problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computational Aspects of Cooperative Game Theory
• Fractional matchings and the Edmonds-Gallai theorem
• scientific article; zbMATH DE number 5485541 (Why is no real title available?)
• scientific article; zbMATH DE number 3557552 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• scientific article; zbMATH DE number 3361920 (Why is no real title available?)
• Integer and Fractional Matchings
• Node-and edge-deletion NP-complete problems
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Solutions for the stable roommates problem with payments
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• The assignment game. I: The core
• The bargaining problem
• The complexity of König subgraph problems and above-guarantee vertex cover
• The cooperative game theory foundations of network bargaining games
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(18)

• The stable fixtures problem with payments
• Stabilizing network bargaining games by blocking players
• Simple games versus weighted voting games: bounding the critical threshold value
• Minimum cost stability in exchange networks
• Tractability of König edge deletion problems
• Additive stabilizers for unstable graphs
• Stabilizing weighted graphs
• Core stability of vertex cover games
• Graph stabilization: a survey
• Stabilizing weighted graphs
• Efficient stabilization of cooperative matching games
• Finding small stabilizers for unstable graphs
• Stabilization of capacitated matching games
• A survey of parameterized algorithms and the complexity of edge modification
• The complexity of matching games: a survey
• Stabilization of capacitated matching games
• Von Neumann-Morgenstern stability and internal closedness in matching theory
• Spectral aspects of symmetric matrix signings

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)