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

DOI10.1016/J.DAM.2020.04.002MaRDI QIDQ2184673zbMATH OpenOpenAlexFDO

Authors F. Couto, Sylvain Gravier, Sulamita Klein, Vinícius F. dos Santos, Luerbio 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 characterizationgraph sandwich problemprobe problem\( ( k\ell )\)-cographdichotomy P vs NP-completeness

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the complexity of probe and sandwich problems for generalized threshold graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• Characterizing –partitionable Cographs
• On the forbidden induced subgraph probe and sandwich problems

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A simple linear time LexBFS cograph recognition algorithm.
• A simple linear time algorithm for cograph recognition
• A survey of the algorithmic aspects of modular decomposition
• Characterizing –partitionable Cographs
• Chordal bipartite completion of colored graphs
• Complement reducible graphs
• Graph Sandwich Problems
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• On probe classes of graphs
• On the complexity of probe and sandwich problems for generalized threshold graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Partitions of graphs into one or two independent sets and cliques
• Probe threshold and probe trivially perfect graphs
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY

Cited in

(6)

• Partitions and well-coveredness: the graph sandwich problem
• Characterisations and Linear-Time Recognition of Probe Cographs
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• On the forbidden induced subgraph probe and sandwich problems
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• On the complexity of probe and sandwich problems for generalized threshold graphs

Describes a project that uses

Uses Software

• IMP

This page was built for publication: Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

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