Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
From MaRDI portal
Publication:1933639
DOI10.1016/j.ejc.2012.04.008zbMath1448.68465OpenAlexW2137012936WikidataQ57359649 ScholiaQ57359649MaRDI QIDQ1933639
Michael R. Fellows, Bart M. P. Jansen, Frances A. Rosamond
Publication date: 24 January 2013
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2012.04.008
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (54)
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Structural parameterizations with modulator oblivion ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Meta-kernelization with structural parameters ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ The complexity of degree anonymization by vertex addition ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ What Is Known About Vertex Cover Kernelization? ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Exploiting a hypergraph model for finding Golomb rulers ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ On explaining integer vectors by few homogeneous segments ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ FPT is characterized by useful obstruction sets ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ The parameterized complexity of the minimum shared edges problem ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Structural parameterizations of Tracking Paths problem ⋮ On structural parameterizations for the 2-club problem ⋮ On sparsification for computing treewidth ⋮ Using patterns to form homogeneous teams ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ Myhill-Nerode Methods for Hypergraphs ⋮ Fine-grained parameterized complexity analysis of graph coloring problems
This page was built for publication: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
