Open AccessThe Black-and-White Coloring Problem on Trees
Author(s) -
Daniel Berend,
Shira Zucker
Publication year - 2009
Publication title -
journal of graph algorithms and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.387
H-Index - 38
ISSN - 1526-1719
DOI - 10.7155/jgaa.00180
Subject(s) - white (mutation) , computer science , mathematics , combinatorics , chemistry , biochemistry , gene
Given a graph G and positive integers b and w, the black-and-white coloring problem asks about the existence of a partial vertex-coloring of G, with b vertices colored black and w white, such that there is no edge between a black and a white vertex. We suggest an improved algorithm for solving this problem on trees.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom