Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
GRAY CODES FOR THE IDEALS OF INTERVAL ORDERS
Autore:
HABIB M; NOURINE L; STEINER G;
Indirizzi:
UNIV MONTPELLIER 2,LAB INFORMAT ROBOT & MICROELECT MONTPELLIER,UMR CNRS UM 2 C55060,161 RUE ADA F-34392 MONTPELLIER 5 FRANCE MCMASTER UNIV HAMILTON ON L8S 4M4 CANADA
Titolo Testata:
Journal of algorithms
fascicolo: 1, volume: 25, anno: 1997,
pagine: 52 - 66
SICI:
0196-6774(1997)25:1<52:GCFTIO>2.0.ZU;2-Q
Fonte:
ISI
Lingua:
ENG
Soggetto:
LINEAR EXTENSIONS; ALGORITHM; POSET;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Science Citation Index Expanded
Citazioni:
21
Recensione:
Indirizzi per estratti:
Citazione:
M. Habib et al., "GRAY CODES FOR THE IDEALS OF INTERVAL ORDERS", Journal of algorithms, 25(1), 1997, pp. 52-66

Abstract

The generation of combinatorial objects in a Gray code manner means that the difference between successive objects is small. e.g., one element for subsets or one transposition for permutations of a set. The existence of such Gray codes is often equivalent to an appropriately defined graph on these objects bring Hamiltonian. We show that if the graph G is the covering graph of the lattice of the order ideals of an interval order, then G(2) has a Hamiltonian path. This leads to an algorithm to generate the ideals of interval orders in constant time per ideal. We also prove that the subgraph of G(2) induced by the ideals of any fixed cardinality also has a Hamiltonian path. This proves a conjecture of Pruesse and Ruskey for interval orders, We also show how these paths can be combined into a layered Hamiltonian path of G(2), yielding a Gray code on the ideals in nondecreasing order of their cardinalities. (C) 1997 Academic Press.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 05/04/20 alle ore 13:37:11