Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1648261,
author = {Bhore, Sujoy and Ganian, Robert and Montecchiani, Fabrizio and Nollenburg, Martin},
address = {USA},
booktitle = {Graph Drawing and Network Visualization - 27th International Symposium, GD 2019},
doi = {http://dx.doi.org/10.1007/978-3-030-35802-0_28},
editor = {Daniel Archambault, Csaba D. Toth},
keywords = {Parameterized Complexity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {USA},
isbn = {978-3-030-35801-3},
pages = {365-378},
publisher = {Springer},
title = {Parameterized Algorithms for Book Embedding Problems},
url = {https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_28},
year = {2019}
}
TY - JOUR
ID - 1648261
AU - Bhore, Sujoy - Ganian, Robert - Montecchiani, Fabrizio - Nollenburg, Martin
PY - 2019
TI - Parameterized Algorithms for Book Embedding Problems
PB - Springer
CY - USA
SN - 9783030358013
KW - Parameterized Complexity
UR - https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_28
L2 - https://link.springer.com/chapter/10.1007%2F978-3-030-35802-0_28
N2 - A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thickness, or not fixed, called Book Thickness. Both problems are known to be NP -complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order.
ER -
BHORE, Sujoy, Robert GANIAN, Fabrizio MONTECCHIANI a Martin NOLLENBURG. Parameterized Algorithms for Book Embedding Problems. Online. In Daniel Archambault, Csaba D. Toth. \textit{Graph Drawing and Network Visualization - 27th International Symposium, GD 2019}. USA: Springer, 2019, s.~365-378. ISBN~978-3-030-35801-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-35802-0\_{}28.
|
