Reflections on Multivariate Algorithmics and Problem Parameterization
From MaRDI portal
Publication:3113732
DOI10.4230/LIPIcs.STACS.2010.2495zbMath1230.68096OpenAlexW1511638527MaRDI QIDQ3113732
Publication date: 23 January 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_ab25.html
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (61)
Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Studies in Computational Aspects of Voting ⋮ 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 ⋮ The complexity of probabilistic lobbying ⋮ 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 ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Two-layer planarization parameterized by feedback edge set ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Knapsack problems: a parameterized point of view ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ Aspects of a multivariate complexity analysis for rectangle tiling ⋮ Refining the complexity of the sports elimination problem ⋮ The complexity of degree anonymization by vertex addition ⋮ The parameterized complexity of guarding almost convex polygons ⋮ The effect of homogeneity on the computational complexity of combinatorial data anonymization ⋮ Digraph width measures in parameterized algorithmics ⋮ Towards a dichotomy for the possible winner problem in elections based on scoring rules ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ Exploiting a hypergraph model for finding Golomb rulers ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Parameterizing by the number of numbers ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Multivariate complexity analysis of Swap Bribery ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ On explaining integer vectors by few homogeneous segments ⋮ On families of categorial grammars of bounded value, their learnability and related complexity questions ⋮ Average parameterization and partial kernelization for computing medians ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Parameterized aspects of triangle enumeration ⋮ Efficient Algorithms for Eulerian Extension ⋮ Multivariate Complexity Analysis of Swap Bribery ⋮ 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 ⋮ Alternative Parameterizations for Cluster Editing ⋮ The Effect of Homogeneity on the Complexity of k-Anonymity ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ The parameterized complexity of the minimum shared edges problem ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Network-Based Vertex Dissolution ⋮ On structural parameterizations for the 2-club problem ⋮ Using patterns to form homogeneous teams ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ Myhill-Nerode Methods for Hypergraphs ⋮ A fixed-parameter algorithm for guarding 1.5D terrains
This page was built for publication: Reflections on Multivariate Algorithmics and Problem Parameterization
