Finding maximal linear orders in directed graphs
- To: mathgroup at smc.vnet.net
- Subject: [mg68150] Finding maximal linear orders in directed graphs
- From: scott.moser at gmail.com
- Date: Wed, 26 Jul 2006 02:26:15 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Hi All,
Sorry for the bother, but i have a quick question that i can't
find good refferences for, though i'm sure some math and/or CS
folks have a quick answer for...
If I have a directed graph G on N verticies, how can i find
all the maximal linear orders? That is, i would like to actually find
the sets {H_i} such that the relation '->' restricted to H_i forms a
complete, transitive order. (well, the maximal sets that satisfy
this..)
On a related note, if i have a list of sets, is there a handy way in
Mathematica to find maximal elements of the list (maximal with respect
to set inclusion)?
Any ideas about what people call this, or Mathematica algorithms to do
this, or references to look at, would be greatly appreciated.
Thanks,
Scott