KAM-DIMATIA Series 2004-685 and ITI Series 2004-206. Two algorithms for general list matrix partitions

0106924 - MU-W 20040131 CZ eng V - Výzkumná zpráva
Sgall, Jiří - Feder, T. - Hell, P. - Králď, D.
KAM-DIMATIA Series 2004-685 and ITI Series 2004-206. Two algorithms for general list matrix partitions.
Praha: Charles University, 2004. 15 s.
Grant CEP: GA MŠMT LN00A056; GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z1019905
Klíčová slova: combinatorics * graph coloring * homomorphism
Kód oboru RIV: BA - Obecná matematika

List matrix partitions are restricted binary list constraint satisfaction problems which generalize list homomorphisms and many graph partition problems arising, e.g., in the study of perfect graphs. Most of the existing algorithms apply to concrete small matrices, i.e., to partitions problems, provide algorithms for their solution, and discuss their implications.
Trvalý link: http://hdl.handle.net/11104/0014096