J 2005

Two Algorithms for General List Matrix Partitions

FEDER, T; P HELL; Daniel KRÁĽ a J SGALL

Základní údaje

Originální název

Two Algorithms for General List Matrix Partitions

Autoři

FEDER, T; P HELL; Daniel KRÁĽ a J SGALL

Vydání

PHILADELPHIA, SIAM, 2005

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Označené pro přenos do RIV

Ne

UT WoS

Změněno: 6. 11. 2020 11:09, Mgr. Darina Boukalová

Anotace

V originále

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. The first is an O(n(r+2))-algorithrn for the list M-partition problem where M is any r by r matrix over subsets of {0,1}, which has the "bisplit property". This algorithm can be applied to recognize so-called k-bisplit graphs in polynomial time, yielding a solution of an open problem from [2]. The second is an algorithm running in time (rn)O(logr log n/ log log.n)(n)O(log(2)r) for the list M-partition problem where M is any r x r matrix over subsets of {0,1,..., q - 1}, with the "incomplete property". This algorithm applies to all non-NP-complete list M-partition problems with r = 3, and it improves the running time of the quasi-polynomial algorithm for the "stubborn problem" from [5], and for the "edge-free three-coloring problem" from [12].