| author: | Stavros D. Nikolopoulos and Leonidas Palios |
|---|---|
| title: | On the Recognition of Bipolarizable and P -simplicial Graphs4 |
| keywords: | Bipolarizable (Raspail) graph, P -simplicial graph, perfectly orderable graph, recognition, algorithm, complexity4 |
| abstract: | The classes of Raspail (also known as Bipolarizable) and P -simplicial graphs were introduced by Hoàng and Reed who showed that both classes are perfectly
orderable and admit polynomial-time recognition algorithms
HR1. In this paper, we consider the recognition problem on
these classes of graphs and present algorithms that solve it in
4 O(n m) time. In particular, we prove properties and show that we
can produce bipolarizable and P -simplicial orderings on the
vertices of the input graph 4 G , if such orderings exist, working
only on P s that participate in a 3 P of 4 G . The proposed
recognition algorithms are simple, use simple data structures and
both require O(n + m) space. Additionally, we show how our
recognition algorithms can be augmented to provide certificates,
whenever they decide that G is not bipolarizable or P -simplicial;
the augmentation takes 4 O(n + m) time and space.
Finally, we include a diagram on class inclusions and the
currently best recognition time complexities for a number of
perfectly orderable classes of graphs. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Stavros D. Nikolopoulos and Leonidas Palios (2005),
On the Recognition of Bipolarizable and P -simplicial Graphs,
Discrete Mathematics and Theoretical Computer Science 7, pp. 231-2544 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm070114.ps.gz (143 K) |
| ps-source: | dm070114.ps (444 K) |
| pdf-source: | dm070114.pdf (363 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.