Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Directed paths with few or many colors in colored directed graphs

Share/Save/Bookmark

Li , X. and Zhang, S. and Broersma, H.J. (2000) Directed paths with few or many colors in colored directed graphs. [Report]

[img]
Preview
PDF
151Kb
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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65730
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141195