On weighted efficient total domination

Journal of Discrete Algorithms - Tập 10 - Trang 61-69 - 2012
Oliver Schaudt1
1Institut für Informatik, Arbeitsgruppe Faigle/Schrader, Universität zu Köln, Weyertal 80, 50931 Cologne, Germany

Tài liệu tham khảo

E.M. Bakker, J. van Leeuwen, Some domination problems on trees and on general graphs, technical report RUU-CS-91-22, Department of Information and Computing Sciences, Utrecht University, 1991. Brandstädt, 1999, Graph Classes: A Survey, vol. 3 Brouwer, 1983, Graphs whose neighborhoods have no special cycles, Discrete Mathematics, 47, 177, 10.1016/0012-365X(83)90088-2 Chang, 1995, Weighted independent perfect domination on cocomparability graphs, Discrete Applied Mathematics, 63, 215, 10.1016/0166-218X(94)00067-3 Cockayne, 1980, Total domination in graphs, Networks, 10, 211, 10.1002/net.3230100304 Conforti, 2006, Balanced matrices, Discrete Mathematics, 306, 2411, 10.1016/j.disc.2005.12.033 A. del Val, On 2-SAT and Renamable Horn, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, July 30–August 3, 2000, pp. 279–284. Dyer, 1986, Planar 3DM is NP-complete, Journal of Algorithms, 7, 174, 10.1016/0196-6774(86)90002-7 Fouquet, 1993, A strengthening of Ben Rebeaʼs lemma, Journal of Combinatorial Theory, Series B, 59, 35, 10.1006/jctb.1993.1052 H.N. Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs, PhD thesis, Stanford University, 1974. Grinstead, 1993, Efficient edge domination problems in graphs, Information Processing Letters, 8, 221, 10.1016/0020-0190(93)90084-M Haynes, 1998 Kratochvíl, 1995, Generalized domination in chordal graphs, Nordic Journal of Computing, 2, 41 Lu, 2002, Weighted efficient domination problem on some perfect graphs, Discrete Applied Mathematics, 117, 163, 10.1016/S0166-218X(01)00184-6 Roussopoulos, 1973, A max{m,n} algorithm for determining the graph H from its line graph G, Information Processing Letters, 2, 108, 10.1016/0020-0190(73)90029-X Vazirani, 1994, A theory of alternating paths and blossoms for proving correctness of the O(VE) general graph maximum matching algorithm, Combinatorica, 14, 71, 10.1007/BF01305952