Independent sets with domination constraints

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

Rannsóknarafurð: Framlag til fræðitímaritsRáðstefnugreinritrýni

33 Tilvitnanir (Scopus)

Útdráttur

A ρ-independent set S in a graph is parameterized by a set ρ of non-negative integers that constrains how the independent set S can dominate the remaining vertices (∀v∉S: |N(v)∩S|∈ρ.) For all values of ρ, we classify as either NP-complete or polynomial-time solvable the problems of deciding if a given graph has a ρ-independent set. We complement this with approximation algorithms and inapproximability results, for all the corresponding optimization problems. These approximation results extend also to several related independence problems. In particular, we obtain a m approximation of the Set Packing problem, where m is the number of base elements, as well as a n approximation of the maximum independent set in power graphs Gt, for t even.

Upprunalegt tungumálEnska
Síður (frá-til)39-54
Síðufjöldi16
FræðitímaritDiscrete Applied Mathematics
Bindi99
Númer tölublaðs1-3
DOI
ÚtgáfustaðaÚtgefið - 1 feb. 2000
ViðburðurProceedings of the 1997 5th Twente Workshop on Graphs and Combinatorial Optimization - Enschede, Holland
Tímalengd: 20 maí 199722 maí 1997

Fingerprint

Sökktu þér í rannsóknarefni „Independent sets with domination constraints“. Saman myndar þetta einstakt fingrafar.

Vitna í þetta