All Questions
Tagged with transitivity graphs
5 questions
1
vote
0
answers
56
views
coloring of an interval graph with constraints
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
- 385
2
votes
1
answer
177
views
Like transitive reduction, but removing vertices rather than edges?
Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
- 229
0
votes
2
answers
1k
views
Can someone point out why these directed graphs aren't equivalence relations?
As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
- 11
2
votes
1
answer
69
views
Algorithm for getting symetric vertex sets of undirected graph
For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph.
My definition of symmetric vertex set is:
Let $G$ be a graph with ...
- 325
2
votes
1
answer
936
views
Simplest way to check edge set for transitivity
I'm playing around with tournaments and currently have the problem that I need to check whether a given subset of the edges of a tournament is transitive (it need not be acyclic). I'm aware that I can ...
- 2,019