Algorithms for P-4-comparability graph recognition and acyclic P-4-transitive orientation (EN)

Nikolopoulos, S. D. (EN)

Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής (EL)

Nikolopoulos, S. D. (EN)

We consider two problems pertaining to P-4-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P-4-comparability graph and the problem of producing an acyclic P-4-transitive orientation of a P-4-comparability graph. These problems have been considered by HoAng and Reed who described o(n(4))- and o(n(5))-time algorithms for their solution, respectively, where n is the number of vertices of the input graph. Faster algorithms have recently been presented by Raschle and Simon, and by Nikolopoulos and Palios; the time complexity of these algorithms for either problem is o (n + m(2)), where m is the number of edges of the graph. In this paper we describe O (nm)-time and O (n + m)-space algorithms for the recognition and the acyclic P-4-transitive orientation problems on P-4-comparability graphs. The algorithms rely on properties of the P-4-components of a graph, which we establish, and on the efficient construction of the P4-components by means of the BFS-trees of the complement of the graph rooted at each of its vertices, without however explicitly computing the complement. Both algorithms are simple and use simple data structures. (EN)

perfectly orderable graph (EN)

Πανεπιστήμιο Ιωαννίνων

Ιδρυματικό Αποθετήριο Ολυμπιάς

Σχολή Θετικών Επιστημών

ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"

Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Algorithmica (EN)

Αγγλική γλώσσα

2004

http://olympias.lib.uoi.gr/jspui/handle/123456789/10815