Roman Domination: A Parameterized Perspective | Zendy

Henning Fernau | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Roman Domination: A Parameterized Perspective

Author(s) -

Henning Fernau

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11611257_24

Subject(s) - parameterized complexity , treewidth , perspective (graphical) , computer science , bounded function , parametric statistics , planar graph , dual (grammatical number) , combinatorics , planar , discrete mathematics , pathwidth , mathematics , theoretical computer science , graph , algorithm , artificial intelligence , philosophy , mathematical analysis , linguistics , statistics , computer graphics (images) , line graph

We analyze Roman Domination from a parameterized perspective. More specifically, we prove that this problem is W[2]-complete for general graphs. However, parameterized algorithms are presented for graphs of bounded treewidth and for planar graphs. Moreover, it is shown that a parametric dual of Roman Domination is in ${\mathcal FPT}$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research