کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419087 | 681741 | 2014 | 6 صفحه PDF | دانلود رایگان |
Let TT be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for TT is a subset RR of the rooms such that each vertex of TT is in exactly one room in RR. Given a room-partitioning RR for TT, the exchange algorithm walks from room to room until it finds a second different room-partitioning R′R′. In fact, this algorithm generalizes the Lemke–Howson algorithm for finding a Nash equilibrium for two-person games.In this paper, we show that the running time of the exchange algorithm is not polynomial relative to the number of rooms, by constructing a sequence of (planar) instances, in which the algorithm walks from room to room an exponential number of times. We also show a similar result for the problem of finding a second perfect matching in Eulerian graphs.
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 86–91