Characterizing interval graphs which are probe unit interval graphs

DOI10.1016/J.DAM.2019.02.022MaRDI QIDQ2416421zbMATH OpenOpenAlexWikidataFDO

Authors Luciano N. Grippo

Publication date 23 May 2019

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

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

zbMATH Keywords

interval graphsunit interval graphsprobe unit interval graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Forbidden subgraph characterization of bipartite unit probe interval graphs
• Probe interval and probe unit interval graphs on superclasses of cographs
• Probe interval graphs and probe unit interval graphs on superclasses of cographs
• A characterization of cycle-free unit probe interval graphs
• A characterization of 2-tree probe interval graphs

Cites work

• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 512914 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 2119749 (Why is no real title available?)
• scientific article; zbMATH DE number 1439437 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• 2-tree probe interval graphs have a large obstruction set
• A characterization of cycle-free unit probe interval graphs
• A linear-time algorithm for proper interval graph recognition
• A polynomial time recognition algorithm for probe interval graphs
• Algorithmic graph theory and perfect graphs
• Bipartite probe interval graphs, circular arc graphs, and interval point bigraphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Incidence matrices and interval graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Probe interval graphs and probe unit interval graphs on superclasses of cographs
• Recognition of probe proper interval graphs
• Representation of a finite graph by a set of intervals on the real line
• STACS 2005
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(7)

• On probe interval graphs
• Algorithms and Computation
• Probe interval and probe unit interval graphs on superclasses of cographs
• scientific article; zbMATH DE number 4095511 (Why is no real title available?)
• Forbidden subgraph characterization of bipartite unit probe interval graphs
• Probe interval graphs and probe unit interval graphs on superclasses of cographs
• A characterization of 2-tree probe interval graphs

This page was built for publication: Characterizing interval graphs which are probe unit interval graphs

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