2015/05/04 by Asbjørn Brændeland, Brændeland, Asbjørn
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1505.01140
openalex publication_date 2015/05/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.