On the complexity of probe and sandwich problems for generalized threshold graphs

DOI10.1007/978-3-662-53174-7_22MaRDI QIDQ2827819zbMATH OpenOpenAlexFDO

Authors Sylvain Gravier, Sulamita Klein, F. Couto, Luerbio Faria, Vinícius F. dos Santos

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-53174-7_22

zbMATH Keywords

cograph-(2, 1)graph sandwich problemsjoin of two threshold graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Graph Sandwich Problems
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• On the forbidden induced subgraph probe and sandwich problems

Cites work

• A Linear Recognition Algorithm for Cographs
• A simple linear time algorithm for cograph recognition
• A simple linear time LexBFS cograph recognition algorithm.
• Characterizing –partitionable Cographs
• Chordal bipartite completion of colored graphs
• Complement reducible graphs
• Graph Sandwich Problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• 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
• 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

(3)

• Complexity and algorithms for graph and hypergraph sandwich problems
• On the forbidden induced subgraph probe and sandwich problems
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

Describes a project that uses

Uses Software

• IMP

This page was built for publication: On the complexity of probe and sandwich problems for generalized threshold graphs

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