The Fixed Point Property for Ordered Sets of Interval Dimension 2

Document Type

Article

Publication Date

7-2017

Department

Mathematics

School

Mathematics and Natural Sciences

Abstract

We provide a polynomial time algorithm that identifies if a given finite ordered set is in the class of d2-collapsible ordered sets. For a d2-collapsible ordered set, the algorithm also determines if the ordered set is connectedly collapsible. Because finite ordered sets of interval dimension 2 are d2-collapsible, in particular, the algorithm determines in polynomial time if a given finite ordered set of interval dimension 2 has the fixed point property. This result is also a first step in investigating the complexity status of the question whether a given collapsible ordered set has the fixed point property.

Publication Title

Order

Volume

34

Issue

2

First Page

307

Last Page

322

Link to Full Text

Find in your library

Share

COinS