Robust Geometric Computation
- PDF / 3,666,457 Bytes
- 82 Pages / 547.087 x 737.008 pts Page_size
- 37 Downloads / 153 Views
R
R
Radiocoloring in Planar Graphs 2005; Fotakis, Nikoletseas, Papadopoulou, Spirakis VICKY PAPADOPOULOU Department of Computer Science, University of Cyprus, Nicosia, Cyprus Keywords and Synonyms -coloring; k-coloring; Distance-2 coloring; Coloring the square of the graph Problem Definition Consider a graph G(V ; E). For any two vertices u; v 2 V , d(u; v) denotes the distance of u; v in G. The general problem concerns a coloring of the graph G and it is defined as follows: Definition 1 (k-coloring problem) INPUT: A graph G(V ; E). OUTPUT: A function : V ! f1; : : : ; 1g, called k-coloring of G such that 8u; v 2 V, x 2 f0; 1; : : : ; kg: if d(u; v) k x + 1 then j (u) (v)j = x. OBJECTIVE: Let j (V)j = . Then is the number of colors that ' actually uses (it is usually called order of G under '). The number = maxv2V (v)minu2V (u)+ 1 is usually called the span of G under '. The function ' satisfies one of the following objectives: minimum span: is the minimum possible over all possible functions ' of G; minimum order: is the minimum possible over all possible functions ' of G; Min span order: obtains a minimum span and moreover, from all minimum span assignments, ' obtains a minimum order. Min order span: obtains a minimum order and moreover, from all minimum order assignments, ' obtains a minimum span.
Note that the case k = 1 corresponds to the well known problem of vertex graph coloring. Thus, k-coloring problem (with k as an input) is N P -complete [4]. The case of k-coloring problem where k = 2, is called the Radiocoloring problem. Definition 2 (Radiocoloring Problem (RCP) [7]) INPUT: A graph G(V ; E). OUTPUT: A function ˚ : V ! N such that j˚ (u) ˚ (v)j 2 if d(u; v) = 1 and j˚ (u) ˚ (v)j 1 if d(u; v) = 2. OBJECTIVE: The least possible number (order) needed to radiocolor G is denoted by Xorder (G). The least possible number maxv2V ˚ (v) minu2V ˚ (u) + 1 (span) needed for the radiocoloring of G is denoted as Xspan (G). Function ˚ satisfies one of the followings: Min span RCP: ˚ obtains a minimum span, i. e. ˚ = X s pan (G); Min order RCP: ˚ obtains a minimum order ˚ = Xorder (G); Min span order RCP: obtains a minimum span and moreover, from all minimum span assignments, ˚ obtains a minimum order. Min order span RCP: obtains a minimum order and moreover, from all minimum order assignments, ˚ obtains a minimum span. A related to the RCP problem concerns to the square of a graph G, which is defined as follows: Definition 3 Given a graph G(V ; E), G2 is the graph having the same vertex set V and an edge set E 0 : fu; vg 2 E 0 iff d(u; v) 2 in G. The related problem is to color the square of a graph G, G2 so that no two neighbor vertices (in G2 ) get the same color. The objective is to use a minimum number of colors, denoted as (G 2 ) and called chromatic number of the square of the graph G. [5,6] first observed that for any graph G, X order (G) is the same as the (vertex) chromatic number of G2 , i. e. Xorder (G) = (G 2 ).
721
722
R
Radiocoloring in Planar Graphs
Key
Data Loading...
