0027504 - MÚ 2006 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Feder, T. - Hell, P. - Král´, D. - Sgall, Jiří
Two algorithms for general list matrix partitions.
[Dva algoritmy pro listové dělení matic.]
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). New York, Philadelphia: ACM, SIAM, 2005, s. 870-876. ISBN 0-89871-585-7.
[ACM-SIAM Symposium on Discrete Algorithms/16./. Vancouver (CA), 23.01.2005-25.01.2005]
Grant CEP: GA AV ČR(CZ) IAA1019401; GA MŠMT(CZ) LN00A056
Výzkumný záměr: CEZ:AV0Z10190503
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 into a small number of parts. We focus on two general classes of partition problems, provide algorithms for their solution, and discuss their implications.

Článek navrhuje dva algoritmy pro listové dělení matic.
Trvalý link: http://hdl.handle.net/11104/0117602