{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T13:13:51Z","timestamp":1758633231471},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387555"},{"type":"electronic","value":"9783642387562"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38756-2_27","type":"book-chapter","created":{"date-parts":[[2013,5,20]],"date-time":"2013-05-20T20:43:48Z","timestamp":1369082628000},"page":"261-271","source":"Crossref","is-referenced-by-count":4,"title":["Kernelization and Lower Bounds of the Signed Domination Problem"],"prefix":"10.1007","author":[{"given":"Ying","family":"Zheng","sequence":"first","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M., Niedermeier, R.: Polynomial time data reduction for dominating set. J. ACM\u00a051, 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"27_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, New York (1998)"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput.\u00a037, 1077\u20131106 (2007)","journal-title":"SIAM J. Comput."},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0166-218X(00)00219-5","volume":"108","author":"P. Damaschke","year":"2001","unstructured":"Damaschke, P.: Minus domination in small-degree graphs. Discrete Applied Mathematics\u00a0108, 53\u201364 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Felows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Dunbar, J., Hedetniemi, S., Henning, M., Slater, P.: Signed domination in graphs. Graph Theory, Combinatorics and Applications, 311\u2013322 (1995)","DOI":"10.1016\/0012-365X(94)00329-H"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0012-365X(96)00026-X","volume":"158","author":"O. Favaron","year":"1996","unstructured":"Favaron, O.: Signed domination in regular graphs. Discrete Math.\u00a0158, 287\u2013293 (1996)","journal-title":"Discrete Math."},{"key":"27_CR8","unstructured":"Fernau, H., Rodriguez-Velazquez, J.: Alliances and related parameters in graphs (2012) (manuscript)"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.disc.2004.01.007","volume":"283","author":"R. Hass","year":"2004","unstructured":"Hass, R., Wexler, T.: Signed domination numbers of a graph and its complement. Discrete Math.\u00a0283, 87\u201392 (2004)","journal-title":"Discrete Math."},{"key":"27_CR10","first-page":"101","volume":"12","author":"J. Hattingh","year":"1995","unstructured":"Hattingh, J., Henning, M., Slater, P.: The algorithmic complexity of signed domination in graphs. Australasian Journal of Combinatorics\u00a012, 101\u2013112 (1995)","journal-title":"Australasian Journal of Combinatorics"},{"key":"27_CR11","series-title":"Advanced Topics","volume-title":"Domination in Graphs","author":"T. Haynes","year":"1998","unstructured":"Haynes, T., Hedetniemi, S., Slater, P.: Domination in Graphs. Advanced Topics, vol.\u00a02. CRC Press, New York (1998)"},{"key":"27_CR12","first-page":"263","volume":"43","author":"M. Henning","year":"1996","unstructured":"Henning, M.: Domination in regular graphs. Ars Combinatoria\u00a043, 263\u2013271 (1996)","journal-title":"Ars Combinatoria"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0012-365X(96)00025-8","volume":"158","author":"M. Henning","year":"1996","unstructured":"Henning, M., Slater, P.: Irregularities relating domination parameters in cubic graphs. Discrete Math.\u00a0158, 87\u201398 (1996)","journal-title":"Discrete Math."},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s004930070034","volume":"20","author":"J. Matousek","year":"2000","unstructured":"Matousek, J.: On the signed domination in graphs. Combinatorica\u00a020, 103\u2013108 (2000)","journal-title":"Combinatorica"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"4879","DOI":"10.1016\/j.amc.2010.11.019","volume":"217","author":"M. Nandi","year":"2011","unstructured":"Nandi, M., Parui, S., Adhikari, A.: The domination numbers of cylindrical grid graphs. Applied Mathematics and Computation\u00a0217, 4879\u20134889 (2011)","journal-title":"Applied Mathematics and Computation"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"3373","DOI":"10.1016\/j.disc.2007.06.015","volume":"308","author":"E. Shan","year":"2008","unstructured":"Shan, E., Cheng, T.C.: Remarks on minus (signed) total domination in graphs. Discrete Mathematics\u00a0308, 3373\u20133380 (2008)","journal-title":"Discrete Mathematics"},{"key":"27_CR17","first-page":"135","volume":"30","author":"L.G. Valiant","year":"1991","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Computers\u00a030, 135\u2013140 (1991)","journal-title":"IEEE Trans. Computers"},{"key":"27_CR18","first-page":"30","volume":"9","author":"V.G. Vizing","year":"1963","unstructured":"Vizing, V.G.: The Cartesian product of graphs. Vychisl Sistemy\u00a09, 30\u201343 (1963)","journal-title":"Vychisl Sistemy"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Wang, J., Yang, Y., Guo, J., Chen, J.: Planar graph vertex partition for linear problem kernels. Journal of Computer and System Sciences (2012) (to appear)","DOI":"10.1016\/j.jcss.2012.08.001"},{"key":"27_CR20","unstructured":"West, D.: Introduction to Graph Theory, 2nd edn. Prentice-Hall (2000)"},{"key":"27_CR21","unstructured":"Zheng, Y., Wang, J., Feng, Q., Chen, J.: On parameterized complexity of the signed domination problem. Journal of Mathematical Structures in Computer Science (2012) (to appear)"},{"key":"27_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0012-365X(98)00189-7","volume":"195","author":"Z. Zhang","year":"1999","unstructured":"Zhang, Z., Xu, B., Li, Y., Liu, L.: A note on the lower bounds of signed domination number of a graph. Discrete Math.\u00a0195, 295\u2013298 (1999)","journal-title":"Discrete Math."},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1023\/A:1013782511179","volume":"51","author":"B. Zelinka","year":"2001","unstructured":"Zelinka, B.: Signed total domination number of a graph. Czechoslovak Math.\u00a051, 225\u2013229 (2001)","journal-title":"Czechoslovak Math."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38756-2_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T23:30:51Z","timestamp":1557703851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38756-2_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387555","9783642387562"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38756-2_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}