Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
type: Item
instance of: scholarly article
title: Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
zbMATH Open document ID: 1440.05149
author: F. Couto
author: Sylvain Gravier
author: Sulamita Klein
author: Vinícius F. dos Santos
author: Luerbio Faria
published in: Discrete Applied Mathematics
publication date: 2020-05-29T00:00:00Z
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7206532
zbMATH Keywords: \( ( k
zbMATH Keywords: \ell )\)-cograph
zbMATH Keywords: structural characterization
zbMATH Keywords: probe problem
zbMATH Keywords: graph sandwich problem
zbMATH Keywords: dichotomy P vs NP-completeness
describes a project that uses: IMP
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2020.04.002
OpenAlex ID: W3016417088
cites work: Probe threshold and probe trivially perfect graphs
cites work: Partitions of graphs into one or two independent sets and cliques
cites work: The complexity of some problems related to GRAPH 3-COLORABILITY
cites work: Characterizing –partitionable Cographs
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Q4165164
cites work: Complement reducible graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs
cites work: Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
cites work: On decision and optimization (\(k\),\(l\))-graph sandwich problems
cites work: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
cites work: Q4198056
cites work: Graph Sandwich Problems
cites work: A simple linear time algorithm for cograph recognition
cites work: A survey of the algorithmic aspects of modular decomposition
cites work: On probe classes of graphs
cites work: Chordal bipartite completion of colored graphs
DOI: 10.1016/J.DAM.2020.04.002
description: scientific article; zbMATH DE number 7206532