×

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

Citations:

Zbl 0545.68062
PDFBibTeX XMLCite
Full Text: DOI