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

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

Zbl 0549.00002