Voltar
Artigo Revisado por pares
BIBTEX RIS

On the longest upsequence problem for permutations

2001; Taylor & Francis; Volume: 77; Issue: 1 Linguagem: Inglês

10.1080/00207160108805049

ISSN

1029-0265

Autores

Erkki Mäkinen,

Tópico(s)

Bayesian Methods and Mixture Models

Resumo

Given a permutation of n numbers, its longest upsequence can be found in time O(nlog logn). Finding the longest upsequence (resp. longest downsequence) of a permutation solves the maxi- mum independent set problem (resp. the clique problem)for the corresponding permuta- tion graph. Moreover, we discuss the problem of efficiently constructing the Young tableau for a given permutation.

Referência(s)