The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
type: Item
instance of: scholarly article
title: The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
zbMATH Open document ID: 1347.68166
author: Simone Dantas
author: R. B. Teixeira
author: Luerbio Faria
author: Celina M. H. de Figueiredo
published in: Information Processing Letters
publication date: 2016-01-05T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6526581
zbMATH Keywords: probe graphs
zbMATH Keywords: partition problems
zbMATH Keywords: graph algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2015.11.004
OpenAlex ID: W2154921849
cites work: Partitions of graphs into one or two independent sets and cliques
cites work: The Complexity of the List Partition Problem for Graphs
cites work: Recognition of probe distance-hereditary graphs
cites work: Computing and Combinatorics
cites work: A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More)
cites work: List Partitions
cites work: Reducibility among Combinatorial Problems
cites work: Characterisations and Linear-Time Recognition of Probe Cographs
cites work: Q5387698
DOI: 10.1016/J.IPL.2015.11.004
description: scientific article; zbMATH DE number 6526581