Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1367505, author = {Derňár, Marek and Hliněný, Petr}, address = {Germany}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, doi = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42}, keywords = {crossing number; kernelization; parameterized complexity}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Germany}, isbn = {978-3-95977-009-5}, pages = {"42:1"-"42:10"}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, title = {Crossing Number is Hard for Kernelization}, url = {http://socg2016.cs.tufts.edu/}, year = {2016} }
TY - JOUR ID - 1367505 AU - Derňár, Marek - Hliněný, Petr PY - 2016 TI - Crossing Number is Hard for Kernelization PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Germany SN - 9783959770095 KW - crossing number KW - kernelization KW - parameterized complexity UR - http://socg2016.cs.tufts.edu/ L2 - http://socg2016.cs.tufts.edu/ N2 - The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed-parameter tractable for the parameter k [Grohe, STOC 2001]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge. ER -
DERŇÁR, Marek a Petr HLINĚNÝ. Crossing Number is Hard for Kernelization. Online. In \textit{32nd International Symposium on Computational Geometry (SoCG 2016)}. Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, s.~''42:1''-''42:10'', 10 s. ISBN~978-3-95977-009-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42.
|