On distance   r  ‐dominating and   2  r  ‐independent sets in sparse graphs | Zendy

Dvořák Zdeněk | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On distance r ‐dominating and 2 r ‐independent sets in sparse graphs

Author(s) -

Dvořák Zdeněk

Publication year - 2019

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22426

Subject(s) - mathematics , dominating set , combinatorics , independent set , bounded function , class (philosophy) , constant (computer programming) , set (abstract data type) , discrete mathematics , upper and lower bounds , graph , computer science , mathematical analysis , artificial intelligence , vertex (graph theory) , programming language

Dvořák [European J. Combin. 34 (2013), pp. 833–840] gave a bound on the minimum size of a distance r ‐dominating set in terms of the maximum size of a distance 2 r ‐independent set and generalized coloring numbers, thus obtaining a constant‐factor approximation algorithm for the parameters in any class of graphs with bounded expansion. We improve and clarify this dependence using a linear programming (LP)‐based argument inspired by the work of Bansal and Umboh [Inform. Process. Lett. 122 (2017), pp. 21–24].

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research