The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy

DOI10.1016/J.DAM.2017.02.006zbMath1376.05120OpenAlexW2591673746MaRDI QIDQ1686050

Rafael B. Teixeira, Simone Dantas, Luérbio Faria, Celina M. Herrera de Figueiredo

Publication date: 20 December 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.02.006

zbMATH Keywords

graph algorithmspartition problemsprobe 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) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• On the forbidden induced subgraph sandwich problem
• A characterization of chain probe graphs
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• On probe permutation graphs
• The graph sandwich problem for \(P_4\)-sparse graphs
• Probe threshold and probe trivially perfect graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Partitioning chordal graphs into independent sets and cliques
• Partitions of graphs into one or two independent sets and cliques
• Recognition of probe distance-hereditary graphs
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Matrix partitions of perfect graphs
• Characterizing and recognizing probe block graphs
• A characterization of perfect graphs
• Partitioning cographs into cliques and stable sets
• Characterisations and Linear-Time Recognition of Probe Cographs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• List Partitions
• Graph Sandwich Problems
• Computing and Combinatorics
• Linear-Time Recognition of Probe Interval Graphs

This page was built for publication: The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy