Almost diameter of a house-hole-free graph in linear time via LexBFS
type: Item
instance of: scholarly article
title: Almost diameter of a house-hole-free graph in linear time via LexBFS
zbMATH Open document ID: 0933.05143
DOI: 10.1016/S0166-218X(99)00077-3
author: Feodor F. Dragan
published in: Discrete Applied Mathematics
publication date: 2000-03-22T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1340638
zbMATH Keywords: house-hole-free graph
zbMATH Keywords: house-hole-domino-free graph
zbMATH Keywords: asteroidal triple-free graph
zbMATH Keywords: lexicographic breadth-first search
zbMATH Keywords: eccentricity
zbMATH Keywords: diameter
zbMATH Keywords: linear-time algorithm
MaRDI profile type: Publication
full work available at URL: s0166-218x(99)00077-3
OpenAlex ID: W1993222648
description: scientific article; zbMATH DE number 1340638