SOFSEM 2006: Theory and Practice of Computer Science

DOI10.1007/11611257zbMath1175.68543OpenAlexW2756057450MaRDI QIDQ5897987

Elena Prieto, Frank Dehne, Michael R. Fellows, Frances A. Rosamond, Henning Fernau

Publication date: 14 November 2006

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

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

Constant factor approximation for the weighted partial degree bounded edge packing problem ⋮ A parameterized perspective on packing paths of length two ⋮ Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs ⋮ Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Confronting intractability via parameters ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ Inclusion/exclusion meets measure and conquer ⋮ Lower bounds on the differential of a graph ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ On the Complexity Landscape of the Domination Chain ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ The complexity of finding harmless individuals in social networks ⋮ To close is easier than to open: dual parameterization to \(k\)-median

This page was built for publication: SOFSEM 2006: Theory and Practice of Computer Science