Almost diameter of a house-hole-free graph in linear time via LexBFS (Q1302159): Difference between revisions

Usual algorithms for computing the diameter of an arbitrary graph determine the whole distance matrix. Linear time algorithms are known only for some special classes of graphs, among them trees, maximal outer-planar graphs, interval graphs and distance-hereditary graphs. For some classes defined by forbidden substructures the lexicographic breadth-first search algorithm (LexBFS) computes in linear time a good approximation of the diameter. Let \(d\) and \(e\) be the diameter of a graph \(G\) and the eccentricity of a vertex visited lastly by LexBFS on \(G\). Then \(d-2 \leq e \leq d\) if \(G\) is HH-free, \(d-1 \leq e \leq d\) if \(G\) is HHD-free and \(d = e\) if \(G\) is HHD-free and AT-free. Thereby H, H, D and AT stand for house (the complement of \(P_5\)), hole (a chordless cycle \(C_k\) with \(k \geq 5\)), domino (the bipartite graph obtained from \(C_6\) by adding one chord) and asteroidal triple (an independent set of three vertices such that any two of them are connected by a path avoiding the neighbourhood of the third).