Tagged Probe Interval Graphs

Li Sheng (), Chi Wang and Peisen Zhang
Additional contact information
Li Sheng: Drexel University
Chi Wang: University
Peisen Zhang: Columbia University

Journal of Combinatorial Optimization, 2001, vol. 5, issue 1, No 10, 133-142

Abstract: Abstract A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition.

Keywords: interval graphs; probe interval graphs; tagged probe interval graphs; weakly triangulated graphs; triangulated graphs; perfect graphs; DNA physical mapping (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009850020378 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:1:d:10.1023_a:1009850020378

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009850020378

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().