A graph-theoretic approach to the jump-number problem. (English) Zbl 0563.05029

Syslo, Maciej M.

Graphs and order. The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 185-215 (1985).

[For the entire collection see 549.00002.]
Let \(P\) be a poset and \(L\) a linear extension of \(P\). Let \(s(P,L)\) denote the number of jumps in \(L\) (jumps split \(L\) into chains). The jump-number problem is to evaluate the jump number \(s(P)\), where \[ s(P)=\min \{s(P,L);\text{ L is a linear extension of }P\}, \] and to construct a linear extension of P with \(s(P)\) jumps. In general this problem is known to be NP-complete, but it can be solved efficiently for some special classes of posets. Using the arc representation (posets elements are assigned to arcs) the author solves the jump-number problem for N-free posets efficiently. It is proved that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph. The family of greedy algorithms is developed and their use even for jump-number problems of arbitrary posets is discussed. This leads to the construction of optimal linear extensions for some class of posets. This paper methodically shows how the graph-theoretic approach can be utilized when dealing with certain problems on posets.

Reviewer: M.Křivánek

MSC:

05C20	Directed graphs (digraphs), tournaments
06A06	Partial orders, general
68Q25	Analysis of algorithms and problem complexity

Keywords:

poset; jump-number problem; arc representation; greedy algorithms

Citations:

Zbl 0549.00002