Independent sets with domination constraints

DOI10.1016/S0166-218X(99)00124-9zbMATH Open0939.05063WikidataQ126459136 ScholiaQ126459136MaRDI QIDQ1962033FDOQ1962033

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

Publication date: 20 March 2000

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

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

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)

Cites Work

• Title not available (Why is that?)
• The complexity of satisfiability problems
• Approximating the minimum maximal independence number
• Approximating maximum independent sets by excluding subgraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (23)

• 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
• Truthfulness and Approximation with Value-Maximizing Bidders
• On the parameterized complexity of compact set packing
• Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets
• A Taxonomy of Perfect Domination
• Integral graphs and \((k,\tau )\)-regular sets
• Spectral results on regular graphs with \((k,\tau)\)-regular sets
• Main eigenvalues and \((\kappa ,\tau )\)-regular sets
• An Approximation Result for Matchings in Partitioned Hypergraphs
• 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
• Relations between (κ, τ)-regular sets and star complements

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)