Geometric Ideas for Graph Representation and for Cooperative Game Theory

Fekete, Sandor P. (1997) Geometric Ideas for Graph Representation and for Cooperative Game Theory.
Technical Report , 54 p.


This thesis describes context and contents of six papers that use geometric ideas in graph representation, and in cooperative game theory. The first three articles (available as 95-207, 96-224, 97-273) deal with visibility representations of graphs by objects in three-dimensional space. We give a variety of upper and lower bounds on the sizes of graphs that can be represented, as well as a general technique for proving hardness of non-rigid geometric graph representations. In cooperative game theory (see 93-137, 94-166 and 94-178 ) we study cost allocation and savings distribution for several combinatorial optimization games. In particular, we deal with Traveling Salesman games, Minimum Spanning Tree games, and Matching games. We describe solution concepts that involve geometric ideas, partly by the geometry behind the allocation rules, partly by the structure of related polyhedra.

Download: [img] Postscript
Download (2MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-312
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45