×

Euler complexes (oiks). (English) Zbl 1274.90299

Haouari, M. (ed.) et al., ISCO 2010. International symposium on combinatorial optimization. Papers based on the presentations at the symposium, Hammamet, Tunesia, March 24–26, 2010. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 36, 1289-1293 (2010).
Summary: We present a class of instances of the existence of a second object of a specified type, in fact, of an even number of objects of a specified type, which generalizes the existence of an equilibrium for bimatrix games. The proof is an abstract generalization of the Lemke-Howson algorithm for finding an equilibrium of a bimatrix game.
For the entire collection see [Zbl 1236.90011].

MSC:

90C27 Combinatorial optimization
91A10 Noncooperative games
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Cameron, K.: Thomason’s algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on krawczyk’s graphs. Discrete mathematics 235, 69-77 (2001) · Zbl 0974.05050
[2] Cameron, K.; Edmonds, J.: Some graphic uses of an even number of odd nodes. Annales de l’institut Fourier 49, 815-827 (1999) · Zbl 0927.05052
[3] Edmonds, S. Gaubert and V. Gurvich, Sperner Oiks, this conference
[4] Edmonds, S. Gaubert and V. Gurvich, Scarf Oiks, this conference
[5] J. Edmonds and L. Sanita, On Finding another room-partitioning of the vertices, this conference
[6] Gale, D.: Neighborly and cyclic polytopes. Proceedings of the symposia in pure mathematics (1963) · Zbl 0137.41801
[7] Lemke, C. E.; Jr., J. T. Howson: Equilibrium points of bi-matrix games. SIAM J. Of applied mathematics 12, No. 2, 413-423 (July 1964) · Zbl 0128.14804
[8] Morris, W.: Lemke paths on simple polytopes. Mathematics of operations research 19, 780-789 (1994) · Zbl 0821.90116
[9] Schrijver, Alexander: Combinatorial optimization: polyhedra and efficiency. Algorithms and combinatorics 24 (2003) · Zbl 1041.90001
[10] Thomason, A. G.: Hamiltonian cycles and uniquely edge colourable graphs. Ann. discrete math. 3, 259-268 (1978) · Zbl 0382.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.