Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. On finding another room-partitioning of the vertices
 
conference paper

On finding another room-partitioning of the vertices

Edmonds, Jack
•
Sanità, Laura  
2010
Electronic Notes in Discrete Mathematics
International Symposium on Combinatorial Optimization (ISCO)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1016/j.endm.2010.05.159
Author(s)
Edmonds, Jack
Sanità, Laura  
Date Issued

2010

Published in
Electronic Notes in Discrete Mathematics
Volume

36

Start page

1257

End page

1264

Editorial or Peer reviewed

NON-REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
International Symposium on Combinatorial Optimization (ISCO)

Hammamet

March 24-26, 2010

Available on Infoscience
February 15, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/47416
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés