Graph Coloring
- PDF / 235,868 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 35 Downloads / 265 Views
G
Graph Coloring
9. Gupta, A.: Improved bandwidth approximation for trees and chordal graphs. J. Algorithms 40(1), 24–36 (2001) 10. Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839–858 (2005) 11. Krauthgamer, R., Linial, N., Magen, A.: Metric embeddings– beyond one-dimensional distortion. Discrete Comput. Geom. 31(3), 339–356 (2004) 12. Lee, J.R.: Volume distortion for subsets of Euclidean spaces. In: Proceedings of the 22nd Annual Symposium on Computational Geometry, ACM, Sedona, AZ 2006, pp. 207–216. 13. Linial, N.: Finite metric-spaces—combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians, vol. III, Beijing, 2002, pp. 573–586. Higher Ed. Press, Beijing (2002) 14. Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215–245 (1995) 15. Papadimitriou, C.H.: The NP-completeness of the bandwidth minimization problem. Computing 16(3), 263–270 (1976) 16. Rao, S.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In: Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300– 306. ACM, New York (1999) 17. Strang, G.: Linear algebra and its applications, 2nd edn. Academic Press [Harcourt Brace Jovanovich Publishers], New York (1980) 18. Unger, W.: The complexity of the approximation of the bandwidth problem. In: 39th Annual Symposium on Foundations of Computer Science, IEEE, 8–11 Oct 1998, pp. 82–91. 19. Vempala, S.: Random projection: A new approach to VLSI layout. In: 39th Annual Symposium on Foundations of Computer Science, IEEE, 8–11 Oct 1998, pp. 389–398.
Graph Coloring 1994; Karger, Motwani, Sudan 1998; Karger, Motwani, Sudan MICHAEL LANGBERG Department of Computer Science, The Open University of Israel, Raanana, Israel Keywords and Synonyms Clique cover Problem Definition An independent set in an undirected graph G = (V; E) is a set of vertices that induce a subgraph which does not contain any edges. The size of the maximum independent set in G is denoted by ˛(G). For an integer k, a k-coloring of G is a function : V ! [1 : : : k] which assigns colors to the vertices of G. A valid k-coloring of G is a coloring
in which each color class is an independent set. The chromatic number (G) of G is the smallest k for which there exists a valid k-coloring of G. Finding (G) is a fundamental NP-hard problem. Hence, when limited to polynomial time algorithms, one turns to the question of estimating the value of (G) or to the closely related problem of approximate coloring. Problem 1 (Approximate coloring) INPUT: Undirected graph G = (V; E). OUTPUT: A valid coloring of G with r (G) colors, for some approximation ratio r 1. OBJECTIVE: Minimize r. Let G be a graph of size n. The approximate coloring of G can besolved efficiently within an approximation ratio of r=O
n(log log n)2 log3 n
[12]. This holds also for the approxi-
mation of ˛(G) [8]. These
Data Loading...
