Loading...
Please wait, while we are loading the content...
Similar Documents
The Yin and Yang atomic structure of diamond-free hole-free graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Berry, Anne Brandstädt, Andreas Giakoumakis, Vassilis |
| Copyright Year | 2011 |
| Abstract | We show that the atoms by clique separator decomposition of a diamond-free hole-free graph are of three simple types: clique, matched co-bipartite or chordal bipartite. We present an O(n) time algorithm to recognize these graphs and decompose them into atoms. To do this, we use algorithm LexBFS in a novel fashion. Given the atoms, we show how to compute a minimal triangulation in O(n) time, thereby introducing new algorithms for the minimal triangulation of both matched cobipartite graphs and chordal bipartite graphs. Our results enable us to provide efficient solutions to some enumeration and optimization problems. 1. LIMOS UMR CNRS 6158, Université Blaise Pascal, F-63 173 Aubière, berry@isima.fr 2. Institut für Informatik, Universität Rostock, D-18051 Rostock, Germany, ab@informatik.uni-rostock.de 3. MIS, Université de Picardie Jules Verne, Amiens, France, vassilis.giakoumakis@u-picardie.fr |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.isima.fr/~berry/DF.pdf |
| Alternate Webpage(s) | https://www.isima.fr/~berry/DF.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
