Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number

Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: felsner@inf.fu-berlin.de

Vijay Raghavan
Box 1679-B, CS Department
Vanderbilt University
Nashville, TN 37235, USA
email: raghavan@vuse.vanderbilt.edu

Jeremy Spinrad
Box 1679-B, CS Department
Vanderbilt University
Nashville, TN 37235, USA
email: spin@vuse.vanderbilt.edu

Report B 99-05
March 1999

Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding if an order has width k can be done in O(kn²) time and whether a graph has Dilworth number k can be done in O(k²n²) time.
For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time of width at most 4 in O(n log n).

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-99-05.ps.gz