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

DOI10.1016/J.IPL.2015.11.004MaRDI QIDQ903370zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Searching for a NP-complete probe graph problem
• Partitioned Probe Comparability Graphs
• Partitioned probe comparability graphs
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

Cites work

• 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
• Computing and Combinatorics
• List Partitions
• Partitions of graphs into one or two independent sets and cliques
• Probe split graphs
• Recognition of probe distance-hereditary graphs
• Reducibility among combinatorial problems
• The Complexity of the List Partition Problem for Graphs

Cited in

(6)

• On the probe problem for \((r,\ell )\)-well-coveredness
• On the complexity of probe and sandwich problems for generalized threshold graphs
• 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
• Searching for a NP-complete probe graph problem
• 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)