The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy

DOI10.1016/J.IPL.2015.11.004zbMath1347.68166OpenAlexW2154921849MaRDI QIDQ903370

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

Publication date: 5 January 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.11.004

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ On the probe problem for \((r,\ell )\)-well-coveredness

Cites Work

• Unnamed Item
• Partitions of graphs into one or two independent sets and cliques
• Recognition of probe distance-hereditary graphs
• A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More)
• Characterisations and Linear-Time Recognition of Probe Cographs
• The Complexity of the List Partition Problem for Graphs
• List Partitions
• Reducibility among Combinatorial Problems
• Computing and Combinatorics

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