Fundamentals of parameterized complexity
From MaRDI portal
Publication:383833
DOI10.1007/978-1-4471-5559-1zbMath1358.68006OpenAlexW2116087731MaRDI QIDQ383833
Michael R. Fellows, Rodney G. Downey
Publication date: 6 December 2013
Published in: Texts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4471-5559-1
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)
Related Items (only showing first 100 items - show all)
Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths ⋮ Complexity and monotonicity results for domination games ⋮ On the ordered list subgraph embedding problems ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ Compactors for parameterized counting problems ⋮ A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows ⋮ An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification ⋮ Multistage graph problems on a global budget ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ Sorting by multi-cut rearrangements ⋮ Structural parameterizations of clique coloring ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Structural parameterizations for boxicity ⋮ Win-win kernelization for degree sequence completion problems ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ FO model checking on geometric graphs ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Chordal editing is fixed-parameter tractable ⋮ Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Parameterizing edge modification problems above lower bounds ⋮ On the complexity of connection games ⋮ Treewidth distance on phylogenetic trees ⋮ Solving linear equations parameterized by Hamming weight ⋮ Polynomial kernels and user reductions for the workflow satisfiability problem ⋮ Parameterized approximation algorithms for packing problems ⋮ Rural postman parameterized by the number of components of required edges ⋮ Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory ⋮ Kernelization of edge perfect code and its variants ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ Algorithms for the workflow satisfiability problem engineered for counting constraints ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments ⋮ On the complexity of rainbow coloring problems ⋮ Parameterized complexity of the \(k\)-arc Chinese postman problem ⋮ On the parameterized complexity of b-\textsc{chromatic number} ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ Parameterized algorithms for the module motif problem ⋮ Courcelle's theorem for triangulations ⋮ Do branch lengths help to locate a tree in a phylogenetic network? ⋮ Reconfiguration on nowhere dense graph classes ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ The \(k\)-leaf spanning tree problem admits a klam value of 39 ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Parameterized complexity of superstring problems ⋮ Change-making problems revisited: a parameterized point of view ⋮ Interval scheduling and colorful independent sets ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Refining the complexity of the sports elimination problem ⋮ Algorithms solving the matching cut problem ⋮ The complexity of degree anonymization by vertex addition ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis ⋮ Directed NLC-width ⋮ Confronting intractability via parameters ⋮ Exploiting a hypergraph model for finding Golomb rulers ⋮ Parametrized algorithms for random serial dictatorship ⋮ Path-driven orientation of mixed graphs ⋮ Edge bipartization faster than \(2^k\) ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ The minimum feasible tileset problem ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Minimizing Rosenthal potential in multicast games ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Graph editing to a given degree sequence ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ On the parameterized complexity of the edge monitoring problem ⋮ Unit interval editing is fixed-parameter tractable ⋮ A linear kernel for planar red-blue dominating set ⋮ The complexity of finding effectors ⋮ Graph editing problems with extended regularity constraints ⋮ List H-coloring a graph by removing few vertices ⋮ Computing nearest neighbour interchange distances between ranked phylogenetic trees ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ Fréchet distance between a line and avatar point set ⋮ Dynamic parameterized problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Editing to a planar graph of given degrees ⋮ Classification using proximity catch digraphs ⋮ The parameterised complexity of computing the maximum modularity of a graph ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ Dual parameterization of weighted coloring ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs ⋮ Parameterizations of test cover with bounded test sizes ⋮ Parameterized algorithms for finding square roots
This page was built for publication: Fundamentals of parameterized complexity
