### Abstract

Original language | English |
---|---|

Title of host publication | Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings |

Editors | Z Zhang, L Wu, W Xu, DZ Du |

Place of Publication | Switzerland |

Publisher | Springer |

Pages | 625-636 |

Number of pages | 12 |

ISBN (Print) | 978-3-319-12690-6 |

DOIs | |

Publication status | Published - 2014 |

Event | Conference on Combinatorial Optimization and Applications (COCOA 2014 8th) - Maui, Hawaii, Maui, Hawaii, United States Duration: 19 Dec 2014 → 21 Dec 2014 Conference number: 2014 (8th) |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 8881 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | Conference on Combinatorial Optimization and Applications (COCOA 2014 8th) |
---|---|

Abbreviated title | COCOA |

Country | United States |

City | Maui, Hawaii |

Period | 19/12/14 → 21/12/14 |

### Fingerprint

### Cite this

*Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings*(pp. 625-636). (Lecture Notes in Computer Science; Vol. 8881). Switzerland: Springer. https://doi.org/10.1007/978-3-319-12691-3_47

}

*Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings.*Lecture Notes in Computer Science, vol. 8881, Springer, Switzerland, pp. 625-636, Conference on Combinatorial Optimization and Applications (COCOA 2014 8th), Maui, Hawaii, United States, 19/12/14. https://doi.org/10.1007/978-3-319-12691-3_47

**On the parameterized complexity of dynamic problems with connectivity constraints.** / Abu-Khzam, F.N.; Egan, J.; Fellows, M.R.; Rosamond, F.A.; Shaw, P.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › Research › peer-review

TY - GEN

T1 - On the parameterized complexity of dynamic problems with connectivity constraints

AU - Abu-Khzam, F.N.

AU - Egan, J.

AU - Fellows, M.R.

AU - Rosamond, F.A.

AU - Shaw, P.

PY - 2014

Y1 - 2014

N2 - In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a feasible solution is bounded by some incrementparameter. Parameterized versions of a number of dynamic problems are studied where the solution to the base problem is assumed to be connected. We show that connectivity of solutions plays a positive role with respect to the edit-parameter by proving that the dynamic versions of Connected Dominating Set and Connected Vertex Cover are fixed-parameter tractable with respect to the edit-parameter. On the other hand, the two problems are shown to be W[2]-hard with respect to the increment-parameter. We illustrate further the utility of connected solutions by proving that Dynamic Independent Dominating Set is W[2]-hard with respect to the edit-parameter and we discuss some dynamic versions of maximization problems.

AB - In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a feasible solution is bounded by some incrementparameter. Parameterized versions of a number of dynamic problems are studied where the solution to the base problem is assumed to be connected. We show that connectivity of solutions plays a positive role with respect to the edit-parameter by proving that the dynamic versions of Connected Dominating Set and Connected Vertex Cover are fixed-parameter tractable with respect to the edit-parameter. On the other hand, the two problems are shown to be W[2]-hard with respect to the increment-parameter. We illustrate further the utility of connected solutions by proving that Dynamic Independent Dominating Set is W[2]-hard with respect to the edit-parameter and we discuss some dynamic versions of maximization problems.

KW - Artificial intelligence

KW - Computers, Connected Dominating Set

KW - Connected vertex cover

KW - Connectivity constraints

KW - Dynamic problem

KW - Feasible solution

KW - Independent dominating set

KW - Maximization problem

KW - Parameterized complexity, Parameterization

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-84921455308&doi=10.1007%2f978-3-319-12691-3_47&origin=inward&txGid=df9c2954c222c53971f8f6fed92012d5

U2 - 10.1007/978-3-319-12691-3_47

DO - 10.1007/978-3-319-12691-3_47

M3 - Conference Paper published in Proceedings

SN - 978-3-319-12690-6

T3 - Lecture Notes in Computer Science

SP - 625

EP - 636

BT - Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings

A2 - Zhang, Z

A2 - Wu, L

A2 - Xu, W

A2 - Du, DZ

PB - Springer

CY - Switzerland

ER -