Abstract | ||
---|---|---|
Given a graph $G$ with a total order defined on its vertices, the Maximum Pagenumber-$k$ Subgraph Problem asks for a maximum subgraph $Gu0027$ of $G$ such that $Gu0027$ can be embedded into a $k$-book when the vertices are placed on the spine according to the specified total order. We show that this problem is NP-complete for $k geq 2$. |
Year | Venue | DocType |
---|---|---|
2015 | arXiv: Computational Complexity | Journal |
Volume | Citations | PageRank |
abs/1504.05908 | 0 | 0.34 |
References | Authors | |
7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Jonsson | 1 | 23 | 6.80 |
Marco Kuhlmann | 2 | 309 | 23.06 |