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 (23)

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

This page was built for publication: On probe interval graphs