On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs

DOI10.1007/978-3-662-53174-7_22zbMath1417.05152OpenAlexW2500748935MaRDI QIDQ2827819

Sulamita Klein, Sylvain Gravier, Fernanda Couto, Luérbio Faria, Vinícius Fernandes 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

graph sandwich problemscograph-(2, 1)join of two threshold graphs

Mathematics Subject Classification ID

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

Related Items (1)

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

Uses Software

• IMP

Cites Work

• Unnamed Item
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Complement reducible graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A simple linear time algorithm for cograph recognition
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Partitions of graphs into one or two independent sets and cliques
• Chordal bipartite completion of colored graphs
• Characterizing –partitionable Cographs
• A Linear Recognition Algorithm for Cographs
• Graph Sandwich Problems
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs