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

DOI10.1016/J.DAM.2020.04.002zbMATH Open1440.05149OpenAlexW3016417088MaRDI QIDQ2184673FDOQ2184673

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

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

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)

Cites Work

• Title not available (Why is that?)
• Graph Sandwich Problems
• Complement reducible graphs
• Title not available (Why is that?)
• Partitions of graphs into one or two independent sets and cliques
• Characterizing –partitionable Cographs
• A Linear Recognition Algorithm for Cographs
• Probe threshold and probe trivially perfect graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A simple linear time algorithm for cograph recognition
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• A survey of the algorithmic aspects of modular decomposition
• A simple linear time LexBFS cograph recognition algorithm.
• Chordal bipartite completion of colored graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• 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

Cited In (3)

• Partitions and well-coveredness: the graph sandwich problem
• Characterisations and Linear-Time Recognition of Probe Cographs
• On the forbidden induced subgraph probe and sandwich problems

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)