英和和英

出典:『Wikipedia』 (2007/08/13 04:07 UTC 版)

英語による解説

引用

In graph theory, path coloring usually refers to one of two problems:

• The problem of coloring a (multi)set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors. Set R and graph G are provided at input. This formulation is equivalent to vertex coloring the conflict graph of set R, i.e. a graph with vertex set R and edges connecting all pairs of paths of R which are not edge-disjoint with respect to G.
• The problem of coloring (in accordance with the above definition) any chosen (multi)set R of paths in G, such that the set of pairs of end-vertices of paths from R is equal to some set or multiset I, called a set of requests. Set I and graph G are provided at input. This problem is a special case of a more general class of graph routing problems, known as call scheduling.