On probe interval graphs

DOI10.1016/S0166-218X(98)00077-8zbMath0918.05087MaRDI QIDQ1281778

Chi Wang, Peisen Zhang, Fred R. McMorris

Publication date: 19 August 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

cliques; perfect; probe interval graphs

Mathematics Subject Classification ID

92D20: Protein sequences, DNA sequences

05C75: Structural characterization of families of graphs

Related Items

The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs, Block-graph width, Adjacency matrices of probe interval graphs, A characterization of chain probe graphs, Partitioned probe comparability graphs, On probe permutation graphs, On the bi-enhancement of chordal-bipartite probe graphs, Recognizing edge clique graphs among interval graphs and probe interval graphs, A characterization of cycle-free unit probe interval graphs, Chordal probe graphs, Clique-detection models in computational biochemistry and genomics, 2-tree probe interval graphs have a large obstruction set, Characterisations and Linear-Time Recognition of Probe Cographs

Cites Work

• Unnamed Item
• Unnamed Item
• Weakly triangulated graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Complexity and algorithms for graph and hypergraph sandwich problems
• Permuting matrices to avoid forbidden submatrices
• Incidence matrices and interval graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs