Complexity of domination in triangulated plane graphs

[1] A. Aazami, Domination in graphs with bounded propagation: algorithms, formulations and hardness results, J. Comb. Optim., 19, 4 (2010) 429–456. ⇒17510.1007/s10878-008-9176-7Search in Google Scholar

[2] M. de Berg and A. Khosravi, Optimal binary space partitions for segments in the plane, Int. J. Computational Geometry & Applications22 (2012) 187–206. ⇒17510.1142/S0218195912500045Search in Google Scholar

[3] D. J. Brueni and L. S. Heath, The PMU placement problem, SIAM Journal on Discrete Mathematics19, 3 (2005) 744–761. ⇒17510.1137/S0895480103432556Search in Google Scholar

[4] P. Dorbec, A. González, C. Pennarun, Power domination in maximal planar graphs, manuscript, arXiv:1706.10047 (2017). ⇒175Search in Google Scholar

[5] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co. San Francisco, California: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. ⇒174Search in Google Scholar

[6] W. Goddard, M. A. Henning, Thoroughly Distributed Colorings, manuscript, arXiv:1609.09684 (2016). ⇒177Search in Google Scholar

[7] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning, Domination in graphs applied to electric power networks, SIAM Journal on Discrete Mathematics15, 4 (2002) 519–529. ⇒17510.1137/S0895480100375831Search in Google Scholar

[8] J. Kratochvíl, A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Applied Mathematics52, 3 (1994) 233–252. ⇒17710.1016/0166-218X(94)90143-0Search in Google Scholar

[9] A. Mansfield, Determining the thickness of graphs is NP-hard, Proc. Math. Cambridge Phil. Soc., 39 (1983) 9–23. ⇒17710.1017/S030500410006028XSearch in Google Scholar