|عنوان فارسی مقاله:||آشنایی با فهرست رنگ های گراف|
|عنوان انگلیسی مقاله:||An Introduction to List Colorings of Graphs|
|رشته های مرتبط:||مهندسی کامپیوتر، سخت افزار، معماری سیستم های کامپیوتری . مهندسی نرم افزار|
|فرمت مقالات رایگان||مقالات انگلیسی و ترجمه های فارسی رایگان با فرمت PDF میباشند|
|کیفیت ترجمه||کیفیت ترجمه این مقاله خوب میباشد|
|توضیحات||مقاله انگلیسی ناقص می باشد.|
مقاله انگلیسی رایگان
|دانلود رایگان مقاله انگلیسی|
ترجمه فارسی رایگان
|دانلود رایگان ترجمه مقاله|
|جستجوی ترجمه مقالات||جستجوی ترجمه مقالات مهندسی کامپیوتر|
بخشی از ترجمه فارسی مقاله:
بخشی از مقاله انگلیسی:
One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists.
key words:list coloring- k-Choosability- Planar – Greedy Algorithm
Applications of List Colorings Graph colorings are useful to solve various problems ranging from scheduling  to the channel assignment problem. List colorings in particular arise naturally from applications with restrictions on which values can be assigned to certain objects. In this section, we offer a few examples of these problems and how list colorings are used to solve them. In 3 , Zeitlhofer and Wess describe using list colorings to determine register assignments for computing processes. They discuss a situation with multiple functional units–some capable of addition and multiplication, and some capable of only addition. List coloring is then used for instruction scheduling. For example, if an operation requires a multiplication, it cannot be assigned to an addition-only unit. Thus, each operation is assigned a list of units that can process it, and a list coloring problem emerges. A second list coloring problem arises when assigning registers to store intermediate values. The operations are assigned lists of registers depending on which registers the necessary computation units access, i.e. if an operation requires an addition followed by a multiplication, the intermediate value of the addition should not be stored in a register that is not accessed by a multiplicationcapable unit. Solving these problems then determines an appropriate register assignment and instruction schedule for the desired computation. Because the list coloring problem is NP-hard, Zeitlhofer and Wess take advantage of certain properties of the graphs emerging from their registry assignment problem in order to find a coloring. Another application of list colorings is the channel assignment problem. As Ramachandran, Belding, Almeroth, and Buddhikot discuss in , wireless networks near each other often interfere. Thus, to limit the interference and to satisfy hardware requirements, one must limit the frequencies available to a router. This situation is modeled as a list coloring problem. Ramachandran et al. describe assigning frequencies to a wireless mesh network built on a mixture of multi-radio and single-radio routers. Multi-radio routers have multiple wireless radios which can be tuned to nonoverlapping channels and communicate with severalCourtney L. Baber Chapter 1. Introduction 6 other radios. Single-radio routers, on the other hand, can only be tuned to one channel. In representing this problem as a graph theory problem, it is assumed that the hardware for the network is already in place, so that a network topology is given. Each radio then corresponds to a vertex. Thus, if a router has three radios, that router corresponds to three vertices. Each edge represents a wireless link between radios in the given network topology. Call this graph G. The authors then construct the Multi-radio Conflict Graph (MCG) where each edge in G becomes a vertex. Then if two wireless links in G interfere with each other, an edge is drawn between the vertices in MCG that represent those links. Lists of available frequencies are assigned to each vertex of MCG, and a proper coloring is sought. Ramachandran et al. cope with the difficulty of the list coloring problem by using a breadth-first search algorithm to assign channels to the vertices of MCG. Each network has a gateway router where the network connects to an external network. This router is chosen as the starting point of the breadth-first search since its connections are assumed to host the most traffic. One of the vertices of MCG corresponding to a wireless link with the gateway router will be the first colored, and the coloring will be extended to the rest of MCG in a way that minimizes interference4 . Note that the list coloring problem presented here is actually a list coloring of the edges of G. Edge colorings will be discussed in more detail in Chapter 4.