Parameterized and Exact Computation

DOI10.1007/b100584zbMath1104.68050OpenAlexW2475962691MaRDI QIDQ5311509

Jiong Guo, Rolf Niedermeier, Falk Hüffner

Publication date: 23 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b100584

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01)

Related Items

Parameterized coloring problems on chordal graphs ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Parameterized power domination complexity ⋮ Backdoors to Satisfaction ⋮ A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Separator-based data reduction for signed graph balancing ⋮ A new view on rural postman based on Eulerian extension and matching ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Temporal interval cliques and independent sets ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Aspects of a multivariate complexity analysis for rectangle tiling ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Unnamed Item ⋮ The power of linear-time data reduction for maximum matching ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Constant thresholds can make target set selection tractable ⋮ On explaining integer vectors by few homogeneous segments ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Unnamed Item ⋮ Temporal graph classes: a view through temporal separators ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Parameterized aspects of triangle enumeration ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality ⋮ A fixed parameter algorithm for optimal convex partitions ⋮ Some tractable instances of interval data minmax regret problems ⋮ On finding separators in temporal split and permutation graphs ⋮ Block elimination distance ⋮ The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph ⋮ On finding separators in temporal split and permutation graphs ⋮ Block elimination distance ⋮ Parameterized complexity of diameter ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ Network-Based Vertex Dissolution ⋮ The traveling salesman problem with few inner points

This page was built for publication: Parameterized and Exact Computation