Probe interval graphs and probe unit interval graphs on superclasses of cographs
A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonpr...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2013
|
| Acceso en línea: | Registro en Scopus Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06896caa a22008657a 4500 | ||
|---|---|---|---|
| 001 | PAPER-11280 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204124.0 | ||
| 008 | 190411s2013 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84883317009 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a Probe interval graphs and probe unit interval graphs on superclasses of cographs |
| 260 | |c 2013 | ||
| 270 | 1 | 0 | |m CONICETArgentina |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Bayer, D., Bang Le, V., De Ridder, H.N., Probe threshold and probe trivially perfect graphs (2009) Theoretical Computer Science, 410 (47-49), pp. 4812-4822 | ||
| 504 | |a Brown, D.E., Ludgren, J.R., Bipartite probe interval graphs, circular-arc graphs, and interval point bigraphs (2006) Australasian Journal of Combinatorics, 35, pp. 221-236 | ||
| 504 | |a Brown, D.E., Ludgren, J.R., Sheng, L., Characterization of cycle-free unit probe interval graphs (2009) Discrete Applied Mathematics, 157, pp. 762-767 | ||
| 504 | |a Chandler, D., Chang, D.-M., Kloks, T., Liu, J., Peng, S.-L., On probe permutation graphs (2009) Discrete Applied Mathematics, 157, pp. 2611-2619 | ||
| 504 | |a Chandler, D., Chang, M.-S., Klocks, T., Liu, J., Peng, S.-L., Recognition of probe and partitioned probe distance hereditary graphs (2006) Lecture Notes in Computer Science, 4041, pp. 267-278 | ||
| 504 | |a Chandler, D., Chang, M.-S., Kloks, T., Bang Le, V., Peng, S.-L., Probe ptolemaic graphs (2008) COCOON, pp. 468-477 | ||
| 504 | |a Chv́atal, V., Hammer, P.L., (1975) Aggregation of Inequalities in Integer Programming, , Technical Report CS-TR-75-518, Stanford University | ||
| 504 | |a Giakoumakis, V., Roussel, F., Thuillier, H., On p4-tidy graphs (1997) Discrete Mathematics & Theoretical Computer Science, 1 (1), pp. 17-41 | ||
| 504 | |a Golumbic, M.C., Lipshteyn, M., Chordal probe graphs (2004) Discrete Applied Mathematics, 143 (1-3), pp. 221-237 | ||
| 504 | |a Golumbic, M.C., Trenk, A.N., (2004) Tolerance Graphs, , Cambridge University Press, New York | ||
| 504 | |a Hòang, C., (1985) Perfect Graphs, , PhD thesis, School of Computer Science, McGill University, Montreal | ||
| 504 | |a Jamison, B., Olariu, S., A new class of brittle graphs (1989) Studies in Applied Mathematics, 1203, pp. 89-92 | ||
| 504 | |a Jamison, B., Olariu, S., On a unique tree representation for p4-extendible graphs (1991) Discrete Applied Mathematics, 34, pp. 151-164 | ||
| 504 | |a Le, V.B., De Ridder, H.N., Probe split graphs (2007) Discrete Mathematics & Theoretical Computer Science, 9, p. 1 | ||
| 504 | |a Lekkerkerker, C., Boland, D., Representation of finite graphs by a set of intervals on the real line (1962) Fundamenta Mathematicae, 51, pp. 45-64 | ||
| 504 | |a Liu, J., Zhou, H., Dominating subgraphs in graphs with some forbidden structures (1994) Discrete Mathematics, 135, pp. 163-168 | ||
| 504 | |a Przulj, N., Corneil, D., 2-tree probe interval grahps have a large obstruction set (2005) Discrete Applied Mathematics, 150, pp. 216-231 | ||
| 504 | |a Roberts, F., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , In F. Harary, editor, Academic Press | ||
| 504 | |a Sheng, L., Cycle-free probe interval graphs (1999) Congressus Numerantium, 140, pp. 33-42 | ||
| 504 | |a Tinhofer, G., Strong tree-cographs are birkhoff graphs (1989) Discrete Applied Mathematics, 22 (3), pp. 275-288 | ||
| 504 | |a Wegner, G., (1967) Eigenschaften der Nerven Homologisch-Einfacher Familien in Rn, , PhD thesis, Gottingen | ||
| 504 | |a West, D.B., (2001) Introduction to Graph Theory, , Prentice Hall, New Jersey, USA, second edition | ||
| 504 | |a Zhang, P., Schon, P., Fischer, E., Gayanis, E., Weiss, J., Wistler, S., Bourne, P., An algorithm based on graph theory for the assembly of contigs in physical mapping of dna (1994) Bioinformatics, 10 (3), pp. 309-317 | ||
| 520 | 3 | |a A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe G) graphs with disconnected complement for every graph class G with a companion. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. |l eng | |
| 593 | |a CONICET, Argentina | ||
| 593 | |a Depto. de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Depto. de Matemática and Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile | ||
| 593 | |a Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina | ||
| 690 | 1 | 0 | |a FORBIDDEN INDUCED SUBGRAPHS |
| 690 | 1 | 0 | |a P4-TIDY GRAPHS |
| 690 | 1 | 0 | |a PROBE INTERVAL GRAPHS |
| 690 | 1 | 0 | |a PROBE UNIT INTERVAL GRAPHS |
| 690 | 1 | 0 | |a TREECOGRAPHS |
| 690 | 1 | 0 | |a FORBIDDEN INDUCED SUBGRAPHS |
| 690 | 1 | 0 | |a HUMAN GENOME PROJECT |
| 690 | 1 | 0 | |a INTERVAL GRAPH |
| 690 | 1 | 0 | |a PHYSICAL MAPPING |
| 690 | 1 | 0 | |a PROBE INTERVAL GRAPHS |
| 690 | 1 | 0 | |a PROBE INTERVALS |
| 690 | 1 | 0 | |a TREECOGRAPHS |
| 690 | 1 | 0 | |a UNIT INTERVAL GRAPHS |
| 690 | 1 | 0 | |a FORESTRY |
| 690 | 1 | 0 | |a GRAPHIC METHODS |
| 690 | 1 | 0 | |a PROBES |
| 690 | 1 | 0 | |a TREES (MATHEMATICS) |
| 690 | 1 | 0 | |a FORESTRY |
| 690 | 1 | 0 | |a MATHEMATICS |
| 690 | 1 | 0 | |a TREES |
| 700 | 1 | |a Durán, G. | |
| 700 | 1 | |a Grippo, L.N. | |
| 700 | 1 | |a Safe, M.D. | |
| 773 | 0 | |d 2013 |g v. 15 |h pp. 177-194 |k n. 2 |p Discrete Math. Theor. Comput. Sci. |x 14627264 |w (AR-BaUEN)CENRE-8788 |t Discrete Mathematics and Theoretical Computer Science | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84883317009&partnerID=40&md5=b20285fc0113fc0a0946403f4eb2432f |y Registro en Scopus |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_14627264_v15_n2_p177_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p177_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_14627264_v15_n2_p177_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 72233 | ||