Nordic Journal of Computing Bibliography

Anne Berry, Jean-Paul Bordat, and Pinar Heggernes. Recognizing Weakly Triangulated Graphs by Edge Separability. Nordic Journal of Computing, 7(3):164-177, Fall 2000.
Abstract

We apply Lekkerkerker and Boland's recognition algorithm for triangulated graphs to the class of weakly triangulated graphs. This yields a new characterization of weakly triangulated graphs, as well as a new O(m2) recognition algorithm which, unlike the previous ones, is not based on the notion of a 2-pair, but rather on the structural properties of the minimal separators of the graph. It also gives the strongest relationship to the class of triangulated graphs that has been established so far.

Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

Additional Key Words and Phrases: weakly triangulated graphs, graph recognition, graph characterization, minimal separators, triangulated graphs

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database