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.

Abstract

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.


Actions:
Download: [img] Postscript
Download (2MB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: [error in script] 2 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 91-XX Game theory, economic, social and behavioral sciences > 91Axx Game theory > 91A12 Cooperative games

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C75 Structural characterization of types of graphs

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R05 Combinatorics

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

  • Uncontrolled Keywords: 3-dimensional geometry, complexity, cooperative games, core, cost allocation, graph drawing, graph representation, Held-Karp bound, logic engine, matching, NP-hardness, nucleolus, nucleon, spanning tree, tax, traveling preacher, traveling salesman problem
    Subjects: 91-XX Game theory, economic, social and behavioral sciences > 91Axx Game theory > 91A12 Cooperative games
    05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory
    68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory
    05-XX Combinatorics > 05Cxx Graph theory > 05C75 Structural characterization of types of graphs
    68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R05 Combinatorics
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
    Divisions: Mathematical Institute
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Dec 2011 09:45
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Dec 2011 09:45
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/312