Searching for a NP-complete probe graph problem

MaRDI QIDQ4982373zbMATH OpenFDO

Authors R. B. Teixeira, Simone Dantas, Celina M. H. de Figueiredo

Publication date 9 April 2015

zbMATH Keywords

Londonmistery

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Central limit and other weak theorems (60F05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37)

Recommendations

• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• On the forbidden induced subgraph probe and sandwich problems
• Sandwich and probe problems for excluding paths
• The polynomial dichotomy for three nonempty part sandwich problems

Cited in

(4)

• Sandwich and probe problems for excluding paths
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• The polynomial dichotomy for three nonempty part sandwich problems
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy

This page was built for publication: Searching for a NP-complete probe graph problem

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