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

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)

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

• 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?)
• 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
• 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 \)
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(16)

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