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

DOI10.1016/J.IPL.2015.11.004zbMATH Open1347.68166OpenAlexW2154921849MaRDI QIDQ903370FDOQ903370

Simone Dantas, R. B. Teixeira, Luerbio Faria, Celina M. H. 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Partitions of graphs into one or two independent sets and cliques
• The Complexity of the List Partition Problem for Graphs
• List Partitions
• Characterisations and Linear-Time Recognition of Probe Cographs
• Computing and Combinatorics
• 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)

Cited In (4)

• On the probe problem for \((r,\ell )\)-well-coveredness
• NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k )
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity

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

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