Mason Archival Repository Service

On Maximal Layers Of Random Orders

Show simple item record Banerjee, Indranil 2016-05-19T19:52:51Z 2016-05-19T19:52:51Z 2015-09-24
dc.description.abstract In this thesis we investigate the maximal layers of random partial orders. Main contributions are two-fold. In the first half we investigate the expected size of different maximal layers of a random partial order. In particular when the points are in a plane, we give an enumerative formula for the distribution of the size of these maximal sets. Using Monte- Carlo based simulation we extrapolate the results for higher dimensions. In the second part we explore the computational aspect of the problem. To this end we propose a randomized algorithm for computing the maximal layers and analyze its expected runtime. We show that the expected runtime of our proposed algorithm is bounded by o(kn2) when k is fixed and in the worst case by O(kn2). This is the first non-trivial algorithm whose run-time remains polynomial whenever k is bounded by some polynomial in n while remaining subquadratic in n for constant k. We also extend these results to random orders with arbitrary distributions.
dc.language.iso en en_US
dc.subject posets en_US
dc.subject data structures en_US
dc.subject half-space tree en_US
dc.subject maximal layers en_US
dc.subject random order en_US
dc.title On Maximal Layers Of Random Orders en_US
dc.type Thesis en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search MARS


My Account