Independent sets with domination constraints

DOI10.1016/S0166-218X(99)00124-9MaRDI QIDQ1962033zbMATH OpenWikidataFDO

Authors Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle

Publication date 20 March 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

dominationindependent setalgorithmic complexityIS problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1223713
• On Dominating Sets and Independent Sets of Graphs
• scientific article; zbMATH DE number 1202982
• scientific article; zbMATH DE number 1389216
• Independent domination in finitely defined classes of graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 617552 (Why is no real title available?)
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• scientific article; zbMATH DE number 794265 (Why is no real title available?)
• Approximating maximum independent sets by excluding subgraphs
• Approximating the minimum maximal independence number
• The complexity of satisfiability problems

Cited in

(24)

• Relations between ( , )-regular sets and star complements.
• On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
• Spectral results on graphs with regularity constraints
• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
• On the parameterized complexity of compact set packing
• Shrinking maxima, decreasing costs: new online packing and covering problems
• A constrained independent set problem for matroids
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• An approximation result for matchings in partitioned hypergraphs
• On the parameterized complexity of compact set packing
• Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets
• Truthfulness and approximation with value-maximizing bidders
• Integral graphs and \((k,\tau )\)-regular sets
• A Taxonomy of Perfect Domination
• Spectral results on regular graphs with (k,)-regular sets
• Main eigenvalues and \((\kappa ,\tau )\)-regular sets
• Overflow management with self-eliminations
• Overflow management with self-eliminations
• Branch and recharge: exact algorithms for generalized domination
• Structurally parameterized \(d\)-scattered set
• An overview of \((\kappa, \tau)\)-regular sets and their applications
• Competitive router scheduling with structured data
• Improved (In-)Approximability Bounds for d-Scattered Set
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results

This page was built for publication: Independent sets with domination constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962033)