Extreme rays and diameter conjecture for the oriented-multicut skeleton
Extreme rays and diameter conjecture for the oriented-multicut skeleton
Let be the cone of quasi-semimetrics and the cone generated by oriented multicuts. Let be the skeleton graph of , whose nodes are its extreme rays and whose edges join adjacent extreme rays. A dominating clique is a complete subgraph such that every node is adjacent to at least one of its elements.
Oriented-multicut skeleton conjecture. (i) All oriented multicuts are extreme rays of . (ii) The oriented cuts form a dominating clique in ; consequently, the diameter of is or for every .
The assertions were presented as conjectural general results about the oriented-multicut cone; the surrounding text does not provide a general proof or resolution.
Sources & referencesView supporting material
Primary source
M. Deza, M. Dutour and E. Panteleeva, “Small cones of oriented semi-metrics”, arXiv:math/0111145 (2002).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.