http://www.ccs.neu.edu/home/lieber/evergreen/specker/game.html
Barabasi
Derivative type = graph type
raw material = directed graph
finished product = path in graph
quality = weighted length of path
Underlying inf-max problem:
inf max weight(p)/weight of all edges in G
all graphs G with n all simple paths p in G from A to B
nodes and k edges choose A, B and p.
and type T,
each edge has
a weight,
The type T(p,q) of a graph could be:
T1(p,q) = Each node has at most p outgoing edges and at most q incoming edges.
T2(p,q) = Each node has at least p outgoing edges and at least q incoming edges.
The Longest Path problem is NP-complete:
Find longest simple path. (simple means: no node more than once.)
Don't know paper