Directed paths with few or many colors in colored directed graphs

X. Li, Xueliang Li, S. Zhang, Haitze J. Broersma

Research output: Book/ReportReportProfessional

10 Downloads (Pure)

Abstract

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages16
Publication statusPublished - 2000

Publication series

NameMemorandum Faculteit TW
PublisherUniversity of Twente
No.1543
ISSN (Print)0169-2690

Keywords

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

Cite this

Li, X., Li, X., Zhang, S., & Broersma, H. J. (2000). Directed paths with few or many colors in colored directed graphs. (Memorandum Faculteit TW; No. 1543). Enschede: University of Twente, Department of Applied Mathematics.
Li, X. ; Li, Xueliang ; Zhang, S. ; Broersma, Haitze J. / Directed paths with few or many colors in colored directed graphs. Enschede : University of Twente, Department of Applied Mathematics, 2000. 16 p. (Memorandum Faculteit TW; 1543).
@book{330b8c40c05744a8ae983b23130644a7,
title = "Directed paths with few or many colors in colored directed graphs",
abstract = "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.",
keywords = "EWI-3363, MSC-90C27, IR-65730, MSC-05C85, METIS-141195, MSC-90C35",
author = "X. Li and Xueliang Li and S. Zhang and Broersma, {Haitze J.}",
note = "Imported from MEMORANDA",
year = "2000",
language = "Undefined",
series = "Memorandum Faculteit TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1543",

}

Li, X, Li, X, Zhang, S & Broersma, HJ 2000, 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.

Enschede : University of Twente, Department of Applied Mathematics, 2000. 16 p. (Memorandum Faculteit TW; No. 1543).

Research output: Book/ReportReportProfessional

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 -

Li X, Li X, Zhang S, Broersma HJ. Directed paths with few or many colors in colored directed graphs. Enschede: University of Twente, Department of Applied Mathematics, 2000. 16 p. (Memorandum Faculteit TW; 1543).