Directed paths with few or many colors in colored directed graphs

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

Research output: Book/ReportReportProfessional

12 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