Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

DOI10.1016/j.dam.2020.04.002zbMath1440.05149MaRDI QIDQ2184673

Sylvain Gravier, Sulamita Klein, Vinícius Fernandes dos Santos, Fernanda Couto, Luérbio Faria

Publication date: 29 May 2020

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

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

zbMATH Keywords

structural characterization; graph sandwich problem; probe problem; \( ( k; \ell )\)-cograph; dichotomy P vs NP-completeness

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Uses Software

• IMP