About: Constant-factor approximation of the domination number in sparse graphs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Constant-factor approximation of the domination number in sparse graphs Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1016/j.ejc.2012.12.004
Description	The k-domination number of a graph is the minimum size of a set D such that every vertex of G is at distance at most k from D. We give a linear-time constant-factor algorithm for approximation of the k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, proper classes closed on topological minors and classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge. The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each two vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that vertical bar D vertical bar = 0(vertical bar A vertical bar), and these sets can be found in linear time. For a fixed value of k, the assumptions on the class can be formulated more precisely in terms of generalized coloring numbers. In particular, for the domination number (k = 1), the results hold for all graph classes with arrangeability bounded by a constant. The k-domination number of a graph is the minimum size of a set D such that every vertex of G is at distance at most k from D. We give a linear-time constant-factor algorithm for approximation of the k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, proper classes closed on topological minors and classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge. The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each two vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that vertical bar D vertical bar = 0(vertical bar A vertical bar), and these sets can be found in linear time. For a fixed value of k, the assumptions on the class can be formulated more precisely in terms of generalized coloring numbers. In particular, for the domination number (k = 1), the results hold for all graph classes with arrangeability bounded by a constant. (en)
Title	Constant-factor approximation of the domination number in sparse graphs Constant-factor approximation of the domination number in sparse graphs (en)
skos:prefLabel	Constant-factor approximation of the domination number in sparse graphs Constant-factor approximation of the domination number in sparse graphs (en)
skos:notation	RIV/00216208:11320/13:10159005!RIV14-MSM-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	I
http://linked.open...avai/riv/aktivity	I
http://linked.open...iv/cisloPeriodika	5
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Dvořák, Zdeněk
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	66771
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/13:10159005
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	domination number; coloring number (en)
http://linked.open.../riv/klicoveSlovo	coloring number domination number
http://linked.open...odStatuVydavatele	GB - Spojené království Velké Británie a Severního Irska
http://linked.open...ontrolniKodProRIV	[6561181F8AF9]
http://linked.open...i/riv/nazevZdroje	European Journal of Combinatorics
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	34
http://linked.open...iv/tvurceVysledku	Dvořák, Zdeněk
http://linked.open...ain/vavai/riv/wos	000315936500004
issn	0195-6698
number of pages	8 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.ejc.2012.12.004
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software