Variations on an ordering theme with constraints

We investigate the problem of nding a total order of a nite set that satis es various local ordering constraints. Depending on the admitted constraints, we provide an e cient algorithm or prove NP-completeness. We discuss several generalisations and systematically classify the problems

Guardado en:
Detalles Bibliográficos
Autores principales: Guttmann, Walter, Maucher, Markus
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2006
Materias:
Ciencias Informáticas
Constraints
Algorithms
total ordering
NP-completeness
betweenness
cyclic ordering
topological sorting
computational complexity
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/24376
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
Descripción
Sumario:We investigate the problem of nding a total order of a nite set that satis es various local ordering constraints. Depending on the admitted constraints, we provide an e cient algorithm or prove NP-completeness. We discuss several generalisations and systematically classify the problems

Ejemplares similares