ROMAN DOMINATION: a parameterized perspectiveFootnote†

†A preliminary version of this paper appeared in Proceedings of SOFSEM (2006).

References

• Cockayne , E. J. , Dreyer , P. A. Jr , Hedetniemi , S. M. and Hedetniemi , S. T. 2004 . Roman domination in graphs . Discrete Mathematics , 278 : 11 – 22 .
   Web of Science ®Google Scholar
• Dreyer , P. A. Jr . 2000 . “ Applications and variations of domination in graphs ” . NJ, USA : Rutgers University . PhD thesis
   Google Scholar
• Haynes , T. W. , Hedetniemi , S. T. and Slater , P. J. 1998 . “ Fundamentals of domination in graphs ” . In Monographs and Textbooks in Pure and Applied Mathematics , Vol. 208 , New York : Marcel Dekker .
   Google Scholar
• Stewart , I. December 1999 . Defend the Roman Empire! . Scientific American , : 136 – 139 .
   Web of Science ®Google Scholar
• Benecke , S. 2004 . “ Higher order domination of graphs. Master's thesis, Department of Applied Mathematics ” . South Africa : University of Stellebosch . http://dip.sun.ac.za/vuuren/Theses/Benecke.pdf
   Google Scholar
• Cockayne , E. J. , Grobler , P. J.P. , Gründlingh , W. R. , Munganga , J. and van Vuuren , J. H. 2005 . Protection of a graph . Utilitas Mathematica , 67 : 19 – 32 .
   Web of Science ®Google Scholar
• Goddard , W. D. , Hedetniemi , S. M. and Hedetniemi , S. T. 2005 . Eternal security in graphs . Journal of Combinatorial Mathematics and Combinatorial Computing , 52 : 169 – 180 .
   Google Scholar
• Henning , M. A. 2003 . Defending the Roman Empire from multiple attacks . Discrete Mathematics , 271 : 101 – 115 .
   Web of Science ®Google Scholar
• Henning , M. A. and Hedetniemi , S. T. 2003 . Defending the Roman Empire: a new strategy . Discrete Mathematics , 266 : 239 – 251 .
   Web of Science ®Google Scholar
• Liedloff , M. , Kloks , T. , Liu , J. and Peng , S.-L. 2005 . “ Roman domination over some graphs classes ” . In Graph-Theoretic Concepts in Computer Science, 31st International Workshop , Berlin : Springer-Verlag . WG, LNCS Vol. 3787
   Google Scholar
• Pagourtzis , A. , Penna , P. , Schlude , K. , Steinhöfel , K. , Taylor , D. S. and Widmayer , P. 2002 . “ Server placements, Roman domination and other dominating set variants ” . In Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17^th World Computer Congress — TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science IFIP TCS , Edited by: Baeza-Yates , R. A. , Montanari , U. and Santoro , N. 280 – 291 . Deventer, , The Netherlands : Kluwer .
   Google Scholar
• Downey , R. G. and Fellows , M. R. 1999 . Parameterized Complexity , New York : Springer-Verlag .
   Google Scholar
• Cesati , M. and Di Ianni , M. 1997 . Computation models for parameterized complexity . Mathematical Logic Quarterly , 43 : 179 – 202 .
   Web of Science ®Google Scholar
• Cesati , M. 2003 . The Turing way to parameterized complexity . Journal of Computer and System Sciences , 67 : 654 – 685 .
   Web of Science ®Google Scholar
• Chen , Y. and Flum , J. 2003 . “ Machine characterization of the classes of the W-hierarchy ” . In Computer Science Logic, 17th International Workshop , Edited by: Baaz , M. and Makowsky , J. A. 114 – 127 . Berlin : Springer-Verlag . LNCS Vol. 2803
   Google Scholar
• Fernau , H. 2005 . Parameterized Algorithmics: A Graph-Theoretic Approach , Germany : Universität Tübingen . Habi-li-ta-tions-schrift
   Google Scholar
• Alber , J. , Fan , H. , Fellows , M. R. , Fernau , H. , Niedermeier , R. , Rosamond , F. and Stege , U. 2005 . A refined search tree technique for DOMINATING SET on planar graphs . Journal of Computer and System Sciences , 71 : 385 – 405 .
   Web of Science ®Google Scholar
• Damaschke , P. 2004 . “ Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ” . In International Workshop on Parameterized and Exact Computation—IWPEC 2004 , Edited by: Downey , R. , Fellows , M. and Dehne , F. 1 – 12 . Berlin : Springer-Verlag . LNCS Vol. 3162
   Google Scholar
• Fernau , H. 2002 . “ On parameterized enumeration ” . In Computing and Combinatorics, Proceedings of COCOON 2002 , Edited by: Ibarra , O.H. and Zhang , L. 564 – 573 . Berlin : Springer-Verlag . LNCS Vol. 2383
   Google Scholar
• Kloks , T. 1994 . Treewidth. Computations and Approximations , New York : Springer-Verlag . LNCS Vol. 842
   Google Scholar
• Bodlaender , H. L. 1988 . “ Dynamic programming on graphs with bounded treewidth ” . In Automata, Languages and Programming, Proceedings of the 15th ICALP , Edited by: Lepistö , T. and Salomaa , A. 105 – 119 . New York/Berlin : Springer-Verlag . LNCS Vol. 317
   Google Scholar
• Telle , J. A. and Proskurowski , A. 1993 . “ Practical algorithms on partial k-trees with an application to domination-like problems ” . In Algorithms and Data Structures, Proceedings of the 3rd WADS’93 , Edited by: Dehne , F. 610 – 621 . Berlin : Springer-Verlag . LNCS Vol. 709
   Google Scholar
• Fomin , F. V. and Thilikos , D. M. 2003 . “ Dominating sets in planar graphs: branch-width and exponential speed-up ” . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 168 – 177 . New York : ACM Press .
   Google Scholar
• Dehne , F. , Fellows , M. , Fernau , H. , Prieto , E. and Rosamond , F. 2006 . “ NONBLOCKER SET: parameterized algorithmics for MINIMUM ” . In Software Seminar SOFSEM 2006 , Edited by: Widermann , J. , Tel , G. , Pokorny , J. , Bieliková , M. and Štuller , J. 237 – 245 . Berlin : Springer-Verlag . LNCS Vol. 3831
   Google Scholar