Mendeley出力
＜会議発表論文＞
New Results on Directed Edge Dominating Set
| 作成者 | |
|---|---|
| 本文言語 | |
| 出版者 | |
| 発行日 | |
| 収録物名 | |
| 巻 | |
| 開始ページ | |
| 終了ページ | |
| 会議情報 | |
| 出版タイプ | |
| アクセス権 | |
| 権利関係 | |
| 権利関係 | |
| 関連DOI | |
| 関連DOI | |
| 関連URI | |
| 関連HDL | |
| 関連ISBN | |
| 関連HDL | |
| 関連情報 | |
| 概要 | We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p,q)-Edge Dominating Set. In this problem an arc (u,v) is said to dominate itself, as well as all arcs w...hich are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0,1)-dEDS and (1,1)-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that (p,q)-dEDS is FPT parameterized by p+q+tw, but W-hard parameterized just by tw, where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p,q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.続きを見る |
詳細
| EISSN | |
|---|---|
| レコードID | |
| 関連ISBN | |
| 主題 | |
| 注記 | |
| 助成情報 | |
| 登録日 | 2025.04.25 |
| 更新日 | 2025.04.28 |