The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

被引：8

作者：

van Bevern, Rene ^{[1
,2
]}

Fluschnik, Till ^{[3
]}

Mertzios, George B. ^{[4
]}

Molter, Hendrik ^{[3
]}

Sorge, Manuel ^{[3
,5
]}

Suchy, Ondrej ^{[6
]}

机构：

[1] Novosibirsk State Univ, Novosibirsk, Russia

[2] Russian Acad Sci, Sobolev Inst Math, Siberian Branch, Novosibirsk, Russia

[3] TU Berlin, Inst Softwaretech & Theoret Informat, Berlin, Germany

[4] Univ Durham, Sch Engn & Comp Sci, Durham, England

[5] Ben Gurion Univ Negev, Dept Ind Engn & Management, Beer Sheva, Israel

[6] Czech Tech Univ, Fac Informat Technol, Prague, Czech Republic

来源：

DISCRETE OPTIMIZATION | 2018年 / 30卷

基金：

俄罗斯科学基金会; 英国工程与自然科学研究理事会; 俄罗斯基础研究基金会; 以色列科学基金会;

关键词：

Neighborhood; Feedback vertex set; Vertex deletion; Separator; Dominating set; VERTEX; ENUMERATION; SEPARATION; KERNEL; SET;

D O I：

10.1016/j.disopt.2018.05.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：20 / 50

页数：31

共 50 条

[21] Preprocessing complexity for some graph problems parameterized by structural parameters
Lafond, Manuel
Luo, Weidong
XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 130 - 139
[22] On the complexity of some quorum colorings problems of graphs
Sahbi, Rafik
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 784 - 787
[23] Parameterized Optimization in Uncertain Graphs-A Survey and Some Results
Narayanaswamy, N. S.
Vijayaragunathan, R.
ALGORITHMS, 2020, 13 (01)
[24] Some optimization problems on threshold graphs
Kang, Yu-xia
Xu, Cheng
Zhang, Hua
Wang, Chun-li
Proceedings of the Second International Conference on Game Theory and Applications, 2007, : 95 - 97
[25] Extension of some edge graph problems: Standard, parameterized and approximation complexity
Casel, Katrin
Fernau, Henning
Ghadikolaei, Mehdi Khosravian
Monnot, Jerome
Sikora, Florian
DISCRETE APPLIED MATHEMATICS, 2023, 340 : 183 - 201
[26] On the parameterized complexity of the median and closest problems under some permutation metrics
Luís Cunha
Ignasi Sau
Uéverton Souza
Algorithms for Molecular Biology, 19 (1)
[27] Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen
Fellows, Michael Ralph
TSINGHUA SCIENCE AND TECHNOLOGY, 2014, 19 (04) : 325 - 328
[28] Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen
Michael Ralph Fellows
TsinghuaScienceandTechnology, 2014, 19 (04) : 325 - 328
[29] On the Computational Complexity of Optimization Convex Covering Problems of Graphs
Buzatu, Radu
COMPUTER SCIENCE JOURNAL OF MOLDOVA, 2020, 28 (02) : 187 - 200
[30] On the complexity of some edge-partition problems for graphs
Lonc, Z
DISCRETE APPLIED MATHEMATICS, 1996, 70 (02) : 177 - 183

← 1 2 3 4 5 →