Approximating the minimum maximal independence number
From MaRDI portal
Publication:685520
DOI10.1016/0020-0190(93)90022-2zbMath0778.68041OpenAlexW1976422444MaRDI QIDQ685520
Publication date: 9 January 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90022-2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (42)
Subset sum problems with digraph constraints ⋮ \textsc{MAX MIN} vertex cover and the size of Betti tables ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Stabilization of capacitated matching games ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Approximating Alternative Solutions ⋮ Sparsification and subexponential approximation ⋮ Consistent simplification of polyline tree bundles ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ The many facets of upper domination ⋮ Independent sets with domination constraints ⋮ When polynomial approximation meets exact computation ⋮ Polynomially bounded minimization problems which are hard to approximate ⋮ A scheme to construct distance-three codes using Latin squares, with applications to the \(n\)-cube ⋮ On the max min vertex cover problem ⋮ Complete partitions of graphs ⋮ When polynomial approximation meets exact computation ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ A generalization of maximal independent sets ⋮ Finding minimum hidden guard sets in polygons --- tight approximability results ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ The intractability of computing the Hamming distance ⋮ The complexity of dissociation set problems in graphs ⋮ Smallest independent dominating sets in Kronecker products of cycles ⋮ On the Complexity Landscape of the Domination Chain ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Approximating the minimum independent dominating set in perturbed graphs ⋮ Upper Domination: Complexity and Approximation ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Connected domination of regular graphs ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Some APX-completeness results for cubic graphs ⋮ The b-chromatic number of a graph ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ On approximability of the independent/connected edge dominating set problems ⋮ An Efficient Local Search for the Minimum Independent Dominating Set Problem
Cites Work
This page was built for publication: Approximating the minimum maximal independence number
