On probe interval graphs

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

Peisen Zhang, Chi Wang, Fred R. McMorris

Publication date: 19 August 1999

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00077-8

zbMATH Keywords

cliquesperfectprobe interval graphs

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Structural characterization of families of graphs (05C75)

Related Items

Sandwich and probe problems for excluding paths ⋮ Chordal probe graphs ⋮ Good characterizations and linear time recognition for 2-probe block graphs ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ Adjacency matrices of probe interval graphs ⋮ Characterisations and Linear-Time Recognition of Probe Cographs ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ Recognition of probe proper interval graphs ⋮ A characterization of chain probe graphs ⋮ Partitioned probe comparability graphs ⋮ Recognition of split-graphic sequences ⋮ Block-graph width ⋮ On probe permutation graphs ⋮ Clique-detection models in computational biochemistry and genomics ⋮ On the bi-enhancement of chordal-bipartite probe graphs ⋮ Interval \(k\)-graphs and orders ⋮ A characterization of 2-tree probe interval graphs ⋮ Recognizing edge clique graphs among interval graphs and probe interval graphs ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs ⋮ A characterization of cycle-free unit probe interval graphs ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ 2-tree probe interval graphs have a large obstruction set

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