Digraph Classes and Homomorphism Problems
Speaker:
Arash Rafiey, Indiana State University
Date and Time:
Tuesday, October 10, 2017 - 2:20pm to 2:45pm
Location:
Fields Institute, Room 230
Abstract:
We discuss several of digraph classes and their forbidden obstruction characterizations. Each of theses digraph classes plays an important role in a special type of digraph homomorphism problem. In the digraph homomorphism problem, we are given an input digraph G and a fixed target digraph H and the goal is to find a homomorphism from G to H with certain conditions. List homomorphism problem, minimum cost homomorphism problem, and approximation of minimum cost homomorphism problem are the typical types of the digraph homomorphism problem.