| Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number (2007) | |||||||||||||||
Abstract | |||||||||||||||
| . 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 eÆciently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding deciding if an order has width k can be done in O(kn 2 ) time and whether a graph has Dilworth number k can be done in O(k 2 n 2 ) 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 and of width at most 4 in O(n log n). Mathematics Subject Classications (1991). 05C75, 05C85, 06A07. Key Words. Partial order, width, Dilworth number, recognition algorithms. 1 Introduction The width of a partially ordered set is the size of its largest antichain. Orders of small width are a particularly attractive class since several optimization problems, known to be intractable f... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||