The Linzertorte problem, or a unified approach to painting, baking and weaving
1986; Elsevier BV; Volume: 14; Issue: 1 Linguagem: Inglês
10.1016/0166-218x(86)90004-1
ISSN1872-6771
AutoresDorit S. Hochbaum, Edna Wigderson,
Tópico(s)Limits and Structures in Graph Theory
ResumoWe present complexity models for measuring the complexity of painting, baking and weaving. In the application to painting our aim is to color the vertices of a bipartite graph acccording to some proper 2-coloring while using operations that permit the simultaneous coloring of certain We establish lower bounds on the complexity of the painting problem for general 2-colorable graphs (bipartite) and for the special cases of trees and grid graphs. We then describe algorithms that exactly achieve the lower bounds for grip grahs, Trees anf problems related to baking and weaving.
Referência(s)