
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 22nd, 2013, 06:57 PM  #1 
Newbie Joined: Jan 2013 Posts: 2 Thanks: 0  Maximum number of path for simple acyclic directed graph
Say given a simple acyclic directed graph with n nodes , which includes a starting node s0 and ending node e0 (i.e., a kripke structure without loop) what is the maximum number of path from s0 to e0? 
January 22nd, 2013, 09:59 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Maximum number of path for simple acyclic directed graph
It seems like it's 2^(n2)... at the least this is a lower bound.


Tags 
acyclic, directed, graph, maximum, number, path, simple 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Combinations to navigate a noncyclic directed graph  lfccruz  Applied Math  0  September 3rd, 2013 10:08 PM 
Number of path in Kripke Structure  jack1234  Applied Math  1  January 27th, 2013 03:51 AM 
path dependent function with a definite path  aise5668  Real Analysis  3  March 5th, 2012 07:36 PM 
Number of path components?  skychan  Real Analysis  3  November 5th, 2009 09:10 AM 
Number of directed graphs with no cycles  Rand  Applied Math  4  May 23rd, 2009 06:11 PM 