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
id I19-R120-10915-24376
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Constraints
Algorithms
total ordering
NP-completeness
betweenness
cyclic ordering
topological sorting
computational complexity
spellingShingle Ciencias Informáticas
Constraints
Algorithms
total ordering
NP-completeness
betweenness
cyclic ordering
topological sorting
computational complexity
Guttmann, Walter
Maucher, Markus
Variations on an ordering theme with constraints
topic_facet Ciencias Informáticas
Constraints
Algorithms
total ordering
NP-completeness
betweenness
cyclic ordering
topological sorting
computational complexity
description 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
format Objeto de conferencia
Objeto de conferencia
author Guttmann, Walter
Maucher, Markus
author_facet Guttmann, Walter
Maucher, Markus
author_sort Guttmann, Walter
title Variations on an ordering theme with constraints
title_short Variations on an ordering theme with constraints
title_full Variations on an ordering theme with constraints
title_fullStr Variations on an ordering theme with constraints
title_full_unstemmed Variations on an ordering theme with constraints
title_sort variations on an ordering theme with constraints
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/24376
work_keys_str_mv AT guttmannwalter variationsonanorderingthemewithconstraints
AT mauchermarkus variationsonanorderingthemewithconstraints
bdutipo_str Repositorios
_version_ 1764820467045105665

Ejemplares similares