Depth-first search in split-by-edges trees
Asbjørn Brændeland · arXiv (Cornell University) · 2015
A layerwise search in a split-by-edges tree (as defined by Brændeland, 2015) of agiven graph produces a maximum independent set in exponential time. A depth-first search produces an independent set, which may or may not be a maximum, in linear time, but the worst case success rate is maybe not high enough to make it really interesting. What may make depth-first searching in split-by-edges trees interesting, though, is the pronounced oscillation of its success rate along the graph size axis.