Changes

Jump to: navigation, search

Maximum size of a source-sink reorientable set

82 bytes added, 03:21, 15 May 2014
==Remarks==
By a result of Erdős, Frank, and Kun <ref name="ErFrKu"/> (that can also be derived from Sebő <ref name="Sebo"/>), the maximum size of the union of two [[Sink-stable set|sink-stable setsset]] s can be computed in polynomial time, so the validity of the characterization would imply a polynomial algorithmfor determining the size (but not necessarily for finding a largest source-sink reorientable set).
The following simple example shows that the union of two sink-stable sets (''u'' and ''v'' in the example) may not be [[Sink-stable set|source-sink reorientable]].
1,596
edits