Digraph matrix partitions and trigraph homomorphisms

被引：15

作者：

Feder, Tomas ^{[1
]}

Hell, Pavol

Tucker-Nally, Kim

机构：

[1] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada

[2] Capilano Coll, Dept Math, N Vancouver, BC V7J 3H5, Canada

来源：

DISCRETE APPLIED MATHEMATICS | 2006年 / 154卷 / 17期

关键词：

digraph homomorphisms; trigraph homoniorphisms; list homomorphisms; matrix partition problems; constraint satisfaction problems; complexity dichotomy; NP-complete problems; polynomial time algorithms;

D O I：

10.1016/j.dam.2006.02.009

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Matrix partitions generalize graph colourings and homomorphisms. Their study has so far been confined to symmetric matrices and undirected graphs. In this paper we make an initial study of list matrix partitions for digraphs; in other words our matrices are not necessarily symmetric. We motivate future conjectures by classifying the complexity of all list matrix partition problems for matrices of size up to three. We find it convenient to model the problem in the language of trigraph homomorphisms. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：2458 / 2469

页数：12

共 30 条

[1] Homomorphisms of edge-colored graphs and Coxeter groups
Alon, N
Marshall, TH
[J]. JOURNAL OF ALGEBRAIC COMBINATORICS, 1998, 8 (01) : 5 - 13
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3] Bang-Jensen Jorgen, 1988, SIAM J DISCRETE MATH, V1, P281
[4] Brewster R. C., 1993, THESIS S FRASER U
[5] BREWSTER RC, IN PRESS DISCRETE MA
[6] BULATOV AA, PRGRR0301 OXF U COMP
[7] CAMERON K, SODA 2004
[8] Stable skew partition problem
Dantas, S
de Figueiredo, CMH
Klein, S
Gravier, S
Reed, BA
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) : 17 - 22
[9] Finding skew partitions efficiently
de Figueiredo, CMH
Klein, S
Kohayakawa, Y
Reed, BA
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (02): : 505 - 521
[10] DEFIGUEIREDO CMH, 1996, C NUMER, V119, P217

← 1 2 3 →