Numerous applications of resource partitioning are found in electrical power distribution systems, telecommunication networks, computer networks, fault tolerant systems, grid computing etc. The resource partitioning problem is concerned with finding a resource k-partition of a graph. In this book we present linear algorithms to compute a resource tripartition of a triconnected planar graph and a resource 4-partition of a 4-connected planar graph with base vertices located on the same face of a planar embedding. To solve the resource tripartitioning problem, we have developed a linear- time...

Vertex and edge coloring have their diverse applications in problems such as time tabling and scheduling, frequency assignment for spectrum, register allocation, pattern matching, analysis of biological and archeological data, etc. An l-vertex-coloring is a generalized version of the vertex coloring of a graph with integers that asks assigning colors to vertices such that any two vertices u and v get different colors if dist(u,v) is at most l, where dist(u,v) denotes the length of the shortest path between u and v in G, l being a nonnegative integer. A coloring is optimal if it uses minimum...