Recognition of probe proper interval graphs. (English) Zbl 1284.05218
Summary: In a partitioned probe graph the vertex set is partitioned into probes and non-probes, such that the set of non-probes is an independent set. A probe proper interval graph is the intersection graph of a set of intervals on the line such that every vertex is mapped to an interval, no interval contains another, and two vertices are adjacent if and only if the corresponding intervals intersect and at least one of them is a probe. We present the first linear-time algorithm that determines whether an input partitioned probe graph is a probe proper interval graph, and if the answer is positive then the algorithm constructs a corresponding set of intervals.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | Berry, A.; Golumbic, M. C.; Lipshteyn, M., Recognizing chordal probe graphs and cycle-bicolorable graphs, SIAM J. Discrete Math., 21, 573-591 (2007) · Zbl 1141.05037 |
| [2] | Bonomo, F.; Durán, G.; Grippo, L. N.; Safe, M. D., Probe interval graphs and probe unit interval graphs on superclasses of cographs, Discrete Math. Theor. Comput. Sci., 15, 177-194 (2013) · Zbl 1283.05211 |
| [3] | 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 |
| [4] | Brown, D. E.; Busch, A. H.; Isaak, G., Linear time recognition algorithms and structure theorems for bipartite tolerance graphs and bipartite probe interval graphs, Discrete Math. Theor. Comput. Sci., 12, 63-82 (2010) · Zbl 1280.68142 |
| [5] | Brown, D. E.; Langley, L. J., Forbidden subgraph characterization of bipartite unit probe interval graphs, Australas. J. Combin., 52, 19-31 (2012) · Zbl 1251.05133 |
| [6] | Brown, D. E.; Lundgren, J. R.; Sheng, L., A characterization of cycle-free unit probe interval graphs, Discrete Appl. Math., 157, 762-767 (2009) · Zbl 1172.05345 |
| [7] | Chandler, D. B.; Chang, M.-S.; Kloks, T.; Liu, J.; Peng, S.-L., Partitioned probe comparability graphs, Theoret. Comput. Sci., 396, 212-222 (2008) · Zbl 1145.68037 |
| [8] | Chang, G. J.; Kloks, A. J.J.; Liu, J.; Peng, S.-L., The PIGSs full monty—a floor show of minimal separators, (Diekert, V.; Durand, B., STACS 2005. STACS 2005, LNCS, vol. 3403 (2005), Springer: Springer Heidelberg), 521-532 · Zbl 1118.68509 |
| [9] | Corneil, D. G.; Perl, Y.; Stewart, L. K., Linear recognition algorithm for cographs, SIAM J. Comput., 14, 926-934 (1985) · Zbl 0575.68065 |
| [10] | Deng, X.; Hell, P.; Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput., 25, 390-403 (1996) · Zbl 0858.05094 |
| [12] | Golumbic, M. C.; Kaplan, H.; Shamir, R., On the complexity of DNA physical mapping, Adv. Appl. Math., 15, 251-261 (1994) · Zbl 0806.92007 |
| [13] | Golumbic, M. C.; Lipshteyn, M., On the hierarchy of interval, probe and tolerance graphs, Congr. Numer., 153, 97-106 (2001) · Zbl 0995.05104 |
| [15] | Hell, P.; Shamir, R.; Sharan, R., A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM J. Comput., 31, 289-305 (2002) · Zbl 0992.68065 |
| [16] | Johnson, J. L.; Spinrad, J. P., A polynomial time recognition algorithm for probe interval graphs, (Proc. 12nd Annu. ACM-SIAM Symp. on Discret. Algorithm (2001), ACM-SIAM: ACM-SIAM New York), 477-486 · Zbl 0988.05086 |
| [17] | Le, V. B.; de Ridder, H. N., Characterisations and linear-time recognition of probe cographs, (Brandstädt, A.; Kratsch, D.; Müller, H., WG 2007. WG 2007, LNCS, vol. 4769 (2007), Springer: Springer Heidelberg), 226-237 · Zbl 1141.68537 |
| [18] | Looges, P. J.; Olariu, S., Optimal greedy recognition and coloring for indifference graphs, (Balci, O., Computer Science and Operation Research: New Results at their Interfaces (1992), Pergamon Press: Pergamon Press London), 127-137 |
| [19] | McConnell, R. M.; Nussbaum, Y., Linear-time recognition of probe interval graphs, (Fiat, A.; Sanders, P., ESA 2009. ESA 2009, LNCS, vol. 5757 (2009), Springer: Springer Heidelberg), 349-360, Full version available at: arXiv:1307.5547 [cs.DS] · Zbl 1256.05236 |
| [20] | McConnell, R. M.; Spinrad, J. P., Construction of probe interval models, (Proc. 13th Annu. ACM-SIAM Symp. on Discret. Algorithm (2002), ACM-SIAM: ACM-SIAM New York), 866-875 · Zbl 1058.05060 |
| [21] | McMorris, F. R.; Wang, C.; Zhang, P., On probe interval graphs, Discrete Appl. Math., 88, 315-324 (1998) · Zbl 0918.05087 |
| [23] | Pržulj, N.; Corneil, D. G., 2-Tree probe interval graphs have a large obstruction set, Discrete Appl. Math., 150, 216-231 (2005) · Zbl 1071.92031 |
| [24] | Roberts, F. S., Indifference graphs, (Harary, F., Proof Techniques in Graph Theory (1969), Academic Press: Academic Press New York), 139-146 · Zbl 0193.24205 |
| [25] | Sheng, L., Cycle free probe interval graphs, Congr. Numer., 140, 33-42 (1999) · Zbl 0960.05085 |
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.
