A polynomial time recognition algorithm for probe interval graphs

MaRDI QIDQ2768336zbMATH OpenFDO

Authors Julie L. Johnson, Jeremy P. Spinrad

Publication date 22 July 2002

zbMATH Keywords

DNA sequencingprobe interval graphsrecognition algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Protein sequences, DNA sequences (92D20)

Recommendations

• Recognition of probe proper interval graphs
• On probe interval graphs
• scientific article; zbMATH DE number 4049085

Cited in

(20)

• A linear time recognition algorithm for proper interval graphs
• A characterization of cycle-free unit probe interval graphs
• Chordal probe graphs
• Mining CSTNUDs significant for a set of traces is polynomial
• Good characterizations and linear time recognition for 2-probe block graphs
• Characterizing interval graphs which are probe unit interval graphs
• Recognition of probe proper interval graphs
• 2-tree probe interval graphs have a large obstruction set
• Recognition of Probe Ptolemaic Graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Probe Ptolemaic Graphs
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns
• Algorithms and Computation
• Adjacency matrices of probe interval graphs
• A characterization of chain probe graphs
• Simple linear time recognition of unit interval graphs
• Partitioned probe comparability graphs
• On the bi-enhancement of chordal-bipartite probe graphs
• Recognizing edge clique graphs among interval graphs and probe interval graphs

This page was built for publication: A polynomial time recognition algorithm for probe interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768336)