Journal article
A characterization of cycle-free unit probe interval graphs
Discrete Applied Mathematics, v 157(4), pp 762-767
2009
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
A graph is a
probe interval graph (PIG) if its vertices can be partitioned into probes and nonprobes with an interval assigned to each vertex so that vertices are adjacent if and only if their corresponding intervals overlap and at least one of them is a probe. PIGs are a generalization of interval graphs introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. PIGs have been characterized in the cycle-free case by Sheng, and other miscellaneous results are given by McMorris, Wang, and Zhang. Johnson and Spinrad give a polynomial time recognition algorithm for when the partition of vertices into probes and nonprobes is given. The complexity for the general recognition problem is not known. Here, we restrict attention to the case where all intervals have the same length, that is, we study the
unit probe interval graphs and characterize the cycle-free graphs that are unit probe interval graphs via a list of forbidden induced subgraphs.
Metrics
Details
- Title
- A characterization of cycle-free unit probe interval graphs
- Creators
- David E. Brown - Utah State UniversityJ. Richard Lundgren - Department of Applied Mathematics, University of Colorado at Denver, Denver, CO 80217, United StatesLi Sheng - Drexel University
- Publication Details
- Discrete Applied Mathematics, v 157(4), pp 762-767
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000264226600019
- Scopus ID
- 2-s2.0-59749092244
- Other Identifier
- 991019169566704721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics, Applied