Recognition of probe proper interval graphs

DOI10.1016/j.dam.2013.11.013zbMath1284.05218OpenAlexW2141985769MaRDI QIDQ2440119

Yahav Nussbaum

Publication date: 27 March 2014

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

Full work available at URL: https://doi.org/10.1016/j.dam.2013.11.013

zbMATH Keywords

interval graphgraph recognitionprobe graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Characterizing interval graphs which are probe unit interval graphs ⋮ Unnamed Item ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs

Cites Work

• Partitioned probe comparability graphs
• A characterization of cycle-free unit probe interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On probe interval graphs
• On the complexity of DNA physical mapping
• 2-tree probe interval graphs have a large obstruction set
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• A Linear Recognition Algorithm for Cographs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• STACS 2005
• Linear-Time Recognition of Probe Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Recognition of probe proper interval graphs