12 citations · 24 across the 15 of their papers we have counts for
15 papers
Bounding the edge cover of a hypergraph
Farhad Shahrokhi
Let be a hypergraph. Let , then is an {\it edge cover}, or a {\it set cover}, if . A subset of vertices is {\it indepe…
A performance study of some approximation algorithms for minimum dominating set in a graph
Jonathan S. Li, Rohan Potru, Farhad Shahrokhi
We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm,…
Bounding the trace function of a hypergraph with applications
Farhad Shahrokhi
An upper bound on the trace function of a hypergraph is derived and its applications are demonstrated. For instance, a new upper bound for the VC dimension of , or ,…
A simple upper bound for trace function of a hypergraph with applications
Farhad Shahrokhi
Let be a hypergraph on the vertex set and edge set . We show that number of distinct {\it traces} on any subset of , is most $k.{\hat α…
Strong Pseudo Transitivity and Intersection Graphs
Farhad Shahrokhi
A directed graph is {\it strongly pseudo transitive} if there is a partition of so that graphs and are transitive, and additiona…
Unit Incomparability Dimension and Clique Cover Width in Graphs
Farhad Shahrokhi
For a clique cover in the undirected graph , the {\it clique cover graph} of is the graph obtained by contracting the vertices of each clique in into a single vertex…
Largest reduced neighborhood clique cover number revisited
Farhad Shahrokhi
Let be a graph and . The largest reduced neighborhood clique cover number of , denoted by , is the largest, overall -shallow minors of , of t…
Algorithms For Longest Chains In Pseudo- Transitive Graphs
Farhad Shahrokhi
A directed acyclic graph G = (V, E) is pseudo-transitive with respect to a given subset of edges E1, if for any edge ab in E1 and any edge bc in E, we have ac in E. We give algorit…
On the largest reduced neighborhood clique cover number of a graph
Farhad Shahrokhi
Let be a graph and . A new graph parameter termed the largest reduced neighborhood clique cover number of , denoted by , is introduced. Specifically, $…
Bounds for the Clique Cover Width of Factors of the Apex Graph of the Planar Grid
Farhad Shahrokhi
The {\it clique cover width} of , denoted by , is the minimum value of the bandwidth of all graphs that are obtained by contracting the cliques in a clique cover of …
A new separation theorem with geometric applications
Farhad Shahrokhi
Let be an undirected graph with a measure function assigning non-negative values to subgraphs so that does not exceed the clique cover number of …
Clique Cover Width and Clique Sum
Farhad Shahrokhi
For a clique cover in the undirected graph , the clique cover graph of is the graph obtained by contracting the vertices of each clique in into a single vertex. The…
New separation theorems and sub-exponential time algorithms for packing and piercing of fat objects
Farhad Shahrokhi
For a collection of objects in , let the packing and piercing numbers of , denoted by , and , respectively, be the large…
New representation results for planar graphs
Farhad Shahrokhi
A universal representation theorem is derived that shows any graph is the intersection graph of one chordal graph, a number of co-bipartite graphs, and one unit interval graph. Cen…
A new upper bound for the clique cover number with applications
Farhad Shahrokhi
Let and , denote the size of a largest independent set and the clique cover number of an undirected graph . Let be an interval graph with and $E(G)\…