Computing the jump number on semi-orders is polynomial

Autor:	A. von Arnim, C. de la Higuera
Rok vydání:	1994
Předmět:	Combinatorics Discrete mathematics Polynomial Series (mathematics) Applied Mathematics Serialization Jump Discrete Mathematics and Combinatorics Interval (mathematics) Time complexity Computer Science::Databases Mathematics
Zdroj:	Discrete Applied Mathematics. 51:219-232
ISSN:	0166-218X
DOI:	10.1016/0166-218x(94)90111-2
Popis:	Semi-orders form a subclass of interval orders: they can be represented as sets of intervals of a given length. We first prove that semi-orders can be partitioned by serialization (or series decomposition) without loss of the jump number aspect. On non-serializable semi-orders all linear extensions contain never more than two consecutive bumps (maximal chains of length at most 3). We then give a “divide-and-conquer” argument proving that to solve this case all we need is to be able to compute the number of maximal chains of length at least 2. This can also be dealt with in polynomial time, allowing us to claim that computing the jump number is polynomial on semi-orders.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5c9a1c033f0795df809d4ab7d4fef9b7 https://doi.org/10.1016/0166-218x(94)90111-2 Zobrazit plný text záznamu