×

zbMATH — the first resource for mathematics

Addendum to “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs”. (English) Zbl 0562.68055
In addition to the results in their paper, ibid. 13, 566-579 (1984; Zbl 0545.68062), the authors give here a method for finding an unchorded cycle in a nonchordal graph in time \(O(n+m)\).

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI