21 citations · 64 across the 26 of their papers we have counts for
12 papers · 1 filter
Interval H-graphs : Recognition and forbidden obstructions
Haiko Müller, Arash Rafiey
We introduce the class of interval -graphs, which is the generalization of interval graphs, particularly interval bigraphs. For a fixed graph with vertices $a_1,a_2,\dots,a_…
Interval-Like Graphs and Digraphs
Pavol Hell, Jing Huang, Ross M. McConnell +1
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include,…
Approximation Algorithms for Generalized MST and TSP in Grid Clusters
Binay Bhattacharya, Ante Ćustić, Akbar Rafiey +2
We consider a special case of the generalized minimum spanning tree problem (GMST) and the generalized travelling salesman problem (GTSP) where we are given a set of points inside…
Ordering with precedence constraints and budget minimization
Akbar Rafiey, Jeff Kinne, Ján Manuch +1
We introduce a variation of the scheduling with precedence constraints problem that has applications to molecular folding and production management. We are given a bipartite graph…
Ordering without forbidden patterns
Pavol Hell, Bojan Mohar, Arash Rafiey
Let F be a set of ordered patterns, i.e., graphs whose vertices are linearly ordered. An F-free ordering of the vertices of a graph H is a linear ordering of V(H) such that none of…
Duality for Min-Max Orderings and Dichotomy for Min Cost Homomorphisms
Arash Rafiey, Pavol Hell
Min-Max orderings correspond to conservative lattice polymorphisms. Digraphs with Min-Max orderings have polynomial time solvable minimum cost homomorphism problems. They can also…
Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs
A. Gupta, G. Gutin, M. Karimi +2
For digraphs and , a homomorphism of to is a mapping $f:\ V(G)\dom V(H)$ such that implies . If, moreover, each vertex is…
Minimum Cost Homomorphisms to Reflexive Digraphs
Arvind Gupta, Pavol Hell, Mehdi Karimi +1
For digraphs and , a homomorphism of to is a mapping $f:\ V(G)\dom V(H)$ such that implies . If moreover each vertex is a…
Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
G. Gutin, A. Rafiey, A. Yeo
For digraphs and , a mapping $f: V(D)\dom V(H)$ is a homomorphism of to if implies If, moreover, each vertex is associa…
Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs
G. Gutin, P. Hell, A. Rafiey +1
For graphs and , a mapping $f: V(G)\dom V(H)$ is a homomorphism of to if implies If, moreover, each vertex is associate…
Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs
G. Gutin, A. Rafiey, A. Yeo
For digraphs and , a mapping $f: V(D)\dom V(H)$ is a {\em homomorphism of to } if implies For a fixed directed or undirected graph $H…
Minimum Cost and List Homomorphisms to Semicomplete Digraphs
G. Gutin, A. Rafiey, A. Yeo
The following optimization problem was introduced in \cite{gutinDAM}, where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs $…