Redirigiendo al acceso original de articulo en 24 segundos...
Inicio  /  Algorithms  /  Vol: 12 Par: 9 (2019)  /  Artículo
ARTÍCULO
TITULO

A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

Ronald de Haan and Stefan Szeider    

Resumen

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or higher.

 Artículos similares

       
 
Kefu Yi, Kai Luo, Tuo Chen and Rongdong Hu    
Aimed at the vehicle/pedestrian visual sensing task under low-light conditions and the problems of small, dense objects and line-of-sight occlusion, a nighttime vehicle/pedestrian detection method was proposed. First, a vehicle/pedestrian detection algor... ver más
Revista: Applied Sciences

 
Miroslaw Kowaluk and Andrzej Lingas    
We introduce the concept of a k-dimensional matrix product D of k matrices A1,…,Ak" role="presentation">??1,?,????A1,?,Ak A 1 , ? , A k of sizes n1×n,…,nk×n," role="presentation">??1×??,?,????×??,n1×n,?,nk×n, n 1 ... ver más
Revista: Algorithms

 
Max Bannach and Till Tantau    
Color coding is an algorithmic technique used in parameterized complexity theory to detect ?small? structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pat... ver más
Revista: Algorithms

 
Laurent Bulteau, Guillaume Fertin, Géraldine Jean and Christian Komusiewicz    
A multi-cut rearrangement of a string S is a string ??' S ' obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string ??1·??2·??3·?·????·????+1 X 1 · X... ver más
Revista: Algorithms

 
N. S. Narayanaswamy and R. Vijayaragunathan    
We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) mode... ver más
Revista: Algorithms