Standard

Linear-time computation of a linear problem kernel for dominating set on planar graphs. / Van Bevern, René; Hartung, Sepp; Kammer, Frank et al.

Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers. 2012. p. 194-206 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7112 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Van Bevern, R, Hartung, S, Kammer, F, Niedermeier, R & Weller, M 2012, Linear-time computation of a linear problem kernel for dominating set on planar graphs. in Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7112 LNCS, pp. 194-206, 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, Saarbrucken, Germany, 06.09.2011. https://doi.org/10.1007/978-3-642-28050-4_16

APA

Van Bevern, R., Hartung, S., Kammer, F., Niedermeier, R., & Weller, M. (2012). Linear-time computation of a linear problem kernel for dominating set on planar graphs. In Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers (pp. 194-206). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7112 LNCS). https://doi.org/10.1007/978-3-642-28050-4_16

Vancouver

Van Bevern R, Hartung S, Kammer F, Niedermeier R, Weller M. Linear-time computation of a linear problem kernel for dominating set on planar graphs. In Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers. 2012. p. 194-206. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-28050-4_16

Author

Van Bevern, René ; Hartung, Sepp ; Kammer, Frank et al. / Linear-time computation of a linear problem kernel for dominating set on planar graphs. Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers. 2012. pp. 194-206 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{e693c8c94405417f87267b8bd96d1b21,
title = "Linear-time computation of a linear problem kernel for dominating set on planar graphs",
abstract = "We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G' of size O(γ(G)) with γ(G) = γ(G'). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G'. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.",
author = "{Van Bevern}, Ren{\'e} and Sepp Hartung and Frank Kammer and Rolf Niedermeier and Mathias Weller",
year = "2012",
month = mar,
day = "22",
doi = "10.1007/978-3-642-28050-4_16",
language = "English",
isbn = "9783642280498",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "194--206",
booktitle = "Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers",
note = "6th International Symposium on Parameterized and Exact Computation, IPEC 2011 ; Conference date: 06-09-2011 Through 08-09-2011",

}

RIS

TY - GEN

T1 - Linear-time computation of a linear problem kernel for dominating set on planar graphs

AU - Van Bevern, René

AU - Hartung, Sepp

AU - Kammer, Frank

AU - Niedermeier, Rolf

AU - Weller, Mathias

PY - 2012/3/22

Y1 - 2012/3/22

N2 - We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G' of size O(γ(G)) with γ(G) = γ(G'). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G'. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.

AB - We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G' of size O(γ(G)) with γ(G) = γ(G'). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G'. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.

UR - http://www.scopus.com/inward/record.url?scp=84858397665&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28050-4_16

DO - 10.1007/978-3-642-28050-4_16

M3 - Conference contribution

AN - SCOPUS:84858397665

SN - 9783642280498

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 194

EP - 206

BT - Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers

T2 - 6th International Symposium on Parameterized and Exact Computation, IPEC 2011

Y2 - 6 September 2011 through 8 September 2011

ER -

ID: 22341312