On the forbidden induced subgraph probe and sandwich problems
From MaRDI portal
Publication:1686049
DOI10.1016/j.dam.2016.04.005zbMath1376.05119OpenAlexW2359831704MaRDI QIDQ1686049
Sulamita Klein, Fernanda Couto, Sylvain Gravier, Luérbio Faria
Publication date: 20 December 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.04.005
graph sandwich problemsprobe graphs\((C_4, \ldots, C_{|N|})\)-free graphs\(C_k\)-free graphs\(F\)-free graphs
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)
Related Items
A general method for forbidden induced subgraph sandwich problem NP-completeness, Sandwich and probe problems for excluding paths, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Some completion problems for graphs without chordless cycles of prescribed lengths, The sandwich problem for decompositions and almost monotone properties
Uses Software
Cites Work