Additive stabilizers for unstable graphs

DOI10.1016/j.disopt.2018.08.003zbMath1506.05197arXiv1608.06797OpenAlexW2963086226WikidataQ129304719 ScholiaQ129304719MaRDI QIDQ2419360

Karthekeyan Chandrasekaran, Andreas Wierz, Daniel Schmand, Britta Peis, Jochen Könemann, Corinna Gottschalk

Publication date: 13 June 2019

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.06797

zbMATH Keywords

matchingapproximation algorithmhardnessvertex coverGallai-Edmonds decompositiongraph stabilization

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

The stable fixtures problem with payments ⋮ Stabilization of capacitated matching games ⋮ Stabilizing Weighted Graphs

Cites Work

• Efficient stabilization of cooperative matching games
• The complexity of König subgraph problems and above-guarantee vertex cover
• Finding small stabilizers for unstable graphs
• Network bargaining: using approximate blocking sets to stabilize unstable instances
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Solutions for the stable roommates problem with payments
• The assignment game. I: The core
• Detecting high log-densities
• The Bargaining Problem
• Stabilizing Network Bargaining Games by Blocking Players
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• The Cooperative Game Theory Foundations of Network Bargaining Games
• Multiagent Systems
• Every Monotone Graph Property Is Testable
• Integer and Fractional Matchings
• Vertex packings: Structural properties and algorithms
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Analytical approach to parallel repetition
• Algorithmic Game Theory
• Maximum matching and a polyhedron with 0,1-vertices
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Combinatorial optimization. Theory and algorithms.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Additive stabilizers for unstable graphs