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. / Li, X.; Li, Xueliang; Zhang, S.; Broersma, Haitze J.
Enschede : University of Twente, Department of Applied Mathematics, 2000. 16 p. (Memorandum Faculteit TW; No. 1543).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 -