Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1323060, author = {Hliněný, Petr and Salazar, Gelasio}, address = {Berlin}, booktitle = {International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472}, doi = {http://dx.doi.org/10.1007/978-3-662-48971-0_51}, edition = {LNCS 9472}, editor = {Khaled Elbassioni, Kazuhisa Makino}, keywords = {joint crossing number; crossing minimization}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Berlin}, isbn = {978-3-662-48970-3}, pages = {603-613}, publisher = {Springer Verlag}, title = {On Hardness of the Joint Crossing Number}, year = {2015} }
TY - JOUR ID - 1323060 AU - Hliněný, Petr - Salazar, Gelasio PY - 2015 TI - On Hardness of the Joint Crossing Number PB - Springer Verlag CY - Berlin SN - 9783662489703 KW - joint crossing number KW - crossing minimization N2 - The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar. ER -
HLINĚNÝ, Petr a Gelasio SALAZAR. On Hardness of the Joint Crossing Number. In Khaled Elbassioni, Kazuhisa Makino. \textit{International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472}. LNCS 9472. Berlin: Springer Verlag, 2015, s.~603-613. ISBN~978-3-662-48970-3. Dostupné z: https://dx.doi.org/10.1007/978-3-662-48971-0\_{}51.
|