Stabilizing Weighted Graphs

References

• [1] Ahmadian S, Hosseinzadeh H, Sanità L (2016) Stabilizing network bargaining games by blocking players. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combinatorial Optim. (Springer, Liege, Belgium), 164–177.Google Scholar
• [2] Aspvall B, Shiloach Y (1980) A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM J. Comput. 9(4):827–845.Crossref, Google Scholar
• [3] Balas E (1981) Integer and fractional matchings. Annals of Discrete Mathematics (11): Studies in Integer Programming. Hansen P, ed. North-Holland Mathematical Studies, vol. 59 (North-Holland, Amsterdam), 1–13.Crossref, Google Scholar
• [4] Balinski M (1970) On maximum matching, minimum covering and their connections. Kuhn HW, ed. Proc. Princeton Sympos. Math. Programming (Princeton University Press, Princeton, NJ), 303–312.Google Scholar
• [5] Biró P, Bomhoff M, Golovach PA, Kern W, Paulusma D (2014) Solutions for the stable roommates problem with payments. Theoret. Comput. Sci. 540:53–61.Crossref, Google Scholar
• [6] Biró P, Kern W, Paulusma D (2012) Computing solutions for matching games. Internat. J. Game Theory. 41(1):75–90.Crossref, Google Scholar
• [7] Bock A, Chandrasekaran K, Könemann J, Peis B, Sanità L (2015) Finding small stabilizers for unstable graphs. Math. Programming 154(1–2):173–196.Crossref, Google Scholar
• [8] Chandrasekaran K (2017) Graph stabilization: A survey. Fukunaga T, Kawarabayashi K, eds. Combinatorial Optimization and Graph Algorithms: Communications of NII Shonan Meetings (Springer, Singapore), 21–41.Google Scholar
• [9] Chandrasekaran K, Gottschalk C, Könemann J, Peis B, Schmand D, Wierz A (2019) Additive stabilizers for unstable graphs. Discrete Optim. 31:56–78.Crossref, Google Scholar
• [10] Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1998) Combinatorial Optimization (John Wiley & Sons, Inc., New York).Google Scholar
• [11] Deng X, Ibaraki T, Nagamochi H (1999) Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24(3):751–766.Link, Google Scholar
• [12] Dinur I, Safra S (2005) On the hardness of approximating minimum vertex-cover. Ann. Math. 162(1):439–485.Crossref, Google Scholar
• [13] Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• [14] Ito T, Kakimura N, Kamiyama N, Kobayashi Y, Okamoto Y (2017) Efficient stabilization of cooperative matching games. Theoret. Comput. Sci. 677:69–82.Crossref, Google Scholar
• [15] Khot S (2002) On the power of unique 2-prover 1-round games. Reif JH, ed. Proc. 34th Annual ACM Sympos. Theory Comput. (ACM, Montreal), 767–775.Google Scholar
• [16] Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 – ɛ. J. Comput. System Sci. 74(3):335–349.Crossref, Google Scholar
• [17] Kleinberg JM, Tardos É (2008) Balanced outcomes in social exchange networks. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput. (ACM, Victoria, Canada), 295–304.Google Scholar
• [18] Könemann J, Larson K, Steiner D (2015) Network bargaining: Using approximate blocking sets to stabilize unstable instances. Theory Comput. Syst. 57(3):655–672.Crossref, Google Scholar
• [19] Mishra S, Raman V, Saurabh S, Sikdar S, Subramanian CR (2011) The complexity of König subgraph problems and above-guarantee vertex cover. Algorithmica 61(4):857–881.Crossref, Google Scholar
• [20] Nemhauser GL, Trotter LE Jr (1975) Vertex packings: Structural properties and algorithms. Math. Programming 8(1):232–248.Crossref, Google Scholar
• [21] Ore O (1960) Note on hamilton circuits. Amer. Math. Monthly 67:55.Crossref, Google Scholar
• [22] Shapley LS, Shubik M (1971) The assignment game I: The core. Internat. J. Game Theory 1(1):111–130.Crossref, Google Scholar
• [23] Uhry JP (1975) Sur le problème du couplage maximal. Revue française d’automatique, d’informatique et de recherche opérationnelle. Recherche opérationnelle 9(3):13–20.Google Scholar