### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 16 |

Publication status | Published - 2000 |

### Publication series

Name | Memorandum Faculteit TW |
---|---|

Publisher | University of Twente |

No. | 1543 |

ISSN (Print) | 0169-2690 |

### Keywords

- EWI-3363
- MSC-90C27
- IR-65730
- MSC-05C85
- METIS-141195
- MSC-90C35

### Cite this

*Directed paths with few or many colors in colored directed graphs*. (Memorandum Faculteit TW; No. 1543). Enschede: University of Twente, Department of Applied Mathematics.

}

*Directed paths with few or many colors in colored directed graphs*. Memorandum Faculteit TW, no. 1543, University of Twente, Department of Applied Mathematics, Enschede.

**Directed paths with few or many colors in colored directed graphs.** / Li, X.; Li, Xueliang; Zhang, S.; Broersma, Haitze J.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Directed paths with few or many colors in colored directed graphs

AU - Li, X.

AU - Li, Xueliang

AU - Zhang, S.

AU - Broersma, Haitze J.

N1 - Imported from MEMORANDA

PY - 2000

Y1 - 2000

N2 - Given a graph $D=(V(D),A(D))$ and a coloring of $D$, not necessarily a proper coloring of either the arcs or the vertices of $D$, we consider the complexity of finding a path of $D$ from a given vertex $s$ to another given vertex $t$ with as few different colors as possible, and of finding one with as many different colors as possible. We show that the first problem is polynomial-time solvable, and that the second problem is NP-hard.

AB - Given a graph $D=(V(D),A(D))$ and a coloring of $D$, not necessarily a proper coloring of either the arcs or the vertices of $D$, we consider the complexity of finding a path of $D$ from a given vertex $s$ to another given vertex $t$ with as few different colors as possible, and of finding one with as many different colors as possible. We show that the first problem is polynomial-time solvable, and that the second problem is NP-hard.

KW - EWI-3363

KW - MSC-90C27

KW - IR-65730

KW - MSC-05C85

KW - METIS-141195

KW - MSC-90C35

M3 - Report

T3 - Memorandum Faculteit TW

BT - Directed paths with few or many colors in colored directed graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -