0027504 - MÚ 2006 RIV US eng C - Conference Paper (international conference)
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]
R&D Projects: GA AV ČR(CZ) IAA1019401; GA MŠMT(CZ) LN00A056
Institutional research plan: CEZ:AV0Z10190503
Keywords : combinatorics * graph coloring * homomorphism
Subject RIV: BA - General Mathematics

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.
Permanent Link: http://hdl.handle.net/11104/0117602