An algorithm for solving the jump number problem

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Partial orders, general (06A06) Searching and sorting (68P10) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Review text

Two earlier publications of the author [Order 1, 7-19 (1984; Zbl 0564.06001) and Discrete Math. 63, 279-295 (1987; Zbl 0648.06002)] describe the underlying theory, proofs, and a required algorithm of polynomial complexity to be executed beforehand on a representation specified therein for the posets under consideration: The result is an arc diagram of the poset represented as a digraph returned as adjacency lists of a list of vertices in digraph order such that the poset elements are represented by (directed) poset arcs and the closure of their order is represented by connecting the poset arcs and (directed) dummy arcs in such a manner that the direction of all arcs preserves the order through the vertices. The presented algorithm finds from this digraph an optimal semi-strongly greedy linear sequence of the poset elements, where: optimal: having minimal number of jumps (violations of the poset order between immediate neighbours in the sequence); greedy: each of the chains between the jumps is maximal and does not cover (contain elements greater than) elements following in the sequence; (semi-)strongly greedy: restricted with respect to connection with dummy arcs - mainly: covering of lower elements via dummy arcs not excluded. The algorithm produces the sequence and thereby the number of jumps in time proportional to \(n\cdot k!\) with \(n=set\) size and \(k=number\) of dummy arcs (which may be bounded for a class of sets). Execution times are not given; improvements are discussed; comparison with other algorithms scarce. Some remarks may not be suppressed: 1. Any solving algorithm and its complexity depends on the representation (rules for coding the input) of the poset; the question which representations admit less complexity remains open, not to spak of opimality of the chosen combination. 2. Little trouble brings the definition of the tail of arc/path as the beginning, so digraph direction \(\leftarrow\) corresponds to poset descending \(<\). 3. Acyclic directed graphs (digraphs) should also not contain paths of length 1 (with \(tail=head)\) in addition to such ones of length \(>1\). 4. ``acyclic graphs without loops should not suggest existence of such ones with loops.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: An algorithm for solving the jump number problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113927)