On finding another room-partitioning of the vertices

Jack Edmonds, Laura Sanità

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning of T is a subset R of the rooms such that each vertex of T is in exactly one room in R.We prove that if T has a room-partitioning R, then there is another room-partitioning of T which is different from R. The proof is a simple algorithm which walks from room to room, which however we show to be exponential by constructing a sequence of (planar) instances, where the algorithm walks from room to room an exponential number of times relative to the number of rooms in the instance.We unify the above theorem with Nash's theorem stating that a 2-person game has an equilibrium, by proving a combinatorially simple common generalization.

Original languageEnglish
Pages (from-to)1257-1264
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume36
Issue numberC
DOIs
Publication statusPublished - Aug 2010
Externally publishedYes

Keywords

  • 2-person games
  • Exchange algorithm
  • Room-partitioning

Fingerprint Dive into the research topics of 'On finding another room-partitioning of the vertices'. Together they form a unique fingerprint.

Cite this