Sandwich and probe problems for excluding paths

DOI10.1016/j.dam.2018.05.054zbMath1401.05245OpenAlexW2808699185WikidataQ129700694 ScholiaQ129700694MaRDI QIDQ1627855

Sophie Spirkl, Celina M. Herrera de Figueiredo

Publication date: 3 December 2018

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

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

zbMATH Keywords

graph sandwich problempartitioned probe problemprobe problemunpartitioned probe problem

Mathematics Subject Classification ID

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

Related Items (2)

A general method for forbidden induced subgraph sandwich problem NP-completeness ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover

Cites Work

• On the forbidden induced subgraph sandwich problem
• On probe interval graphs
• On the forbidden induced subgraph probe and sandwich problems
• Complexity and algorithms for reasoning about time
• Graph Sandwich Problems
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs

This page was built for publication: Sandwich and probe problems for excluding paths