Path coloring

Path coloring

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.In both the above problems, the goal is usually to minimise the number of colors used in the coloring. In different variants of path coloring, G may be a simple graph, digraph or multigraph.

External links

* [http://citeseer.ist.psu.edu/erlebach00complexity.html] "The Complexity of Path Coloring and Call Scheduling" by Thomas Erlebach and Klaus Jansen
* [http://www.nada.kth.se/~viggo/wwwcompendium/node122.html] "A compendium of NP optimization problems" by Viggo Kann (problem: Minimum Path Coloring)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • List coloring — In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors, first studied by Vizing [1] and by Erdős, Rubin, and Taylor.[2][3][4] …   Wikipedia

  • Harmonious coloring — of 7 tree with 3 levels using 12 colors. The harmonius chromatic number of this graph is 12 since the vertices are 57, and the color s pair are ncolor*(ncolor 1)/2 >= 57 iff ncolor>=12. Moreover (3/2)*(7+1)=12(see Mitchem s Formula).In graph… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Color-coding — For other uses, see Color code. In computer science and graph theory, the method of color coding[1][2] efficiently finds k vertex simple paths, k vertex cycles, and other small subgraphs within a given graph using probabilistic algorithms, which… …   Wikipedia

  • CPU cache — Cache memory redirects here. For the general use, see cache. A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”