Bipartite permutation graphs. (English) Zbl 0628.05055
It is shown that bipartite permutation graphs have good algorithmic properties in contrast to general bipartite or permutation graphs. Two characterizations of these graphs are presented which lead to a linear time recognition algorithm and also to polynomial algorithms for Hamiltonian problems, a variant of the crossing number problem and the minimum fill-in problem on these graphs.
Reviewer: Ján Plesník (Bratislava)
MSC:
| 05C99 | Graph theory |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C45 | Eulerian and Hamiltonian graphs |
References:
| [1] | Akiyama, T.; Nishizeki, T.; Saito, N., NP-completeness of the Hamilton cycle problem for bipartite graphs, J. Inform. Process., 3, 73-76 (1980) · Zbl 0444.68058 |
| [2] | Brandstädt, A.; Kratsch, D., On the restriction of some NP-complete graph problems to permutation graphs, Forschungsergebnisse Friedrich-Schiller-Universität Jena N/84/80 (1984) · Zbl 0565.05060 |
| [3] | Brandstädt, A.; Kratsch, D., On domination problems for permutation and other graphs, Forschungsergebnisse Friedrich-Schiller-Universität Jena N/85/41 (1985) · Zbl 0588.05047 |
| [4] | Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. System. Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [5] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan Moscow · Zbl 1134.05001 |
| [6] | Colbourn, C. J.; Keil, J. M.; Stewart, L. K., Finding minimum dominating cycles in permutation graphs, Oper. Res. Lett., 4, 13-17 (1985/86) · Zbl 0569.90091 |
| [7] | Colbourn, C. J.; Stewart, L. K., Permutation graphs: connected domination and Steiner trees, Univ. of Waterloo Research Report CS-85-02 (1985) |
| [8] | Colbourn, C. J., On testing isomorphism of permutation graphs, Networks, 11, 13-21 (1981) · Zbl 0459.68031 |
| [9] | Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. ACM, 19, 400-410 (1972) · Zbl 0251.05113 |
| [10] | Farber, M.; Keil, J. M., Domination in permutation graphs, J. Algorithms, 6, 309-321 (1985) · Zbl 0598.05056 |
| [11] | Gallai, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungary, 18, 25-66 (1967) · Zbl 0153.26002 |
| [12] | Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP- Completeness (1979), Freeman: Freeman London · Zbl 0411.68039 |
| [13] | Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003 |
| [14] | Golumbic, M. C., The complexity of comparability graph recognition and coloring, Comput., 18, 199-208 (1977) · Zbl 0365.05025 |
| [15] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press San Francisco · Zbl 0541.05054 |
| [16] | Hopcroft, J. E.; Karp, R. M., A \(n^{5/2}\) algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114 |
| [17] | Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamilton paths in grid graphs, SIAM J. Comput., 11, 676-686 (1982) · Zbl 0506.05043 |
| [18] | Johnson, D. S., The NP-completeness column: an ongoing guide, J. Algorithm, 3, 89-99 (1982) · Zbl 0494.68048 |
| [19] | Johnson, D. S., The NP-completeness column: an ongoing guide, J. Algorithm, 5, 147-160 (1984) · Zbl 0545.68032 |
| [20] | Johnson, D. S., The NP-completeness column: an ongoing guide, J. Algorithm, 6, 434-451 (1985) · Zbl 0608.68032 |
| [21] | Konig, D., Graphen und Matrizen, Mat. Fiz. Lapok, 38, 116-119 (1931) · JFM 57.1340.04 |
| [22] | Krishnamoorthy, M. S., An NP-hard problem in bipartite graphs, SIGACT News, 7, 26-26 (1975) |
| [23] | Nash-Williams, C., Hamilton circuits in graphs and digraphs, (Chartrand, G.; Kapoor, S., The Many Facets of Graph Theory (1969), Springer: Springer New York), 237-243 · Zbl 0195.25902 |
| [24] | Pneuli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permuta-tion graphs, Canad. J. Math., 23, 160-175 (1971) · Zbl 0204.24604 |
| [25] | Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602 |
| [26] | Spinrad, J., Two dimensional partial orders, (Ph.D. Thesis (1982), Princeton Univ. Dept. of EECS: Princeton Univ. Dept. of EECS Berlin) |
| [27] | Spinrad, J., On comparability and permutation graphs, SIAM J. Comput., 14, 658-670 (1985) · Zbl 0568.68051 |
| [28] | G. Steiner and L.K. Stewart, A linear time algorithm to find the jump number of two dimensional bipartite partial orders, submitted for publication.; G. Steiner and L.K. Stewart, A linear time algorithm to find the jump number of two dimensional bipartite partial orders, submitted for publication. · Zbl 0622.06002 |
| [29] | Stewart, L. K., Permutation graph structure and algorithms, (Ph.D. Thesis (1985), Univ. of Toronto, Dept. of Computer Science) |
| [30] | Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 77-79 (1981) · Zbl 0496.68033 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
