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 条
  • [1] Parameterized Complexity of Secluded Connectivity Problems
    Fomin, Fedor V.
    Golovach, Petr A.
    Karpov, Nikolay
    Kulikov, Alexander S.
    THEORY OF COMPUTING SYSTEMS, 2017, 61 (03) : 795 - 819
  • [2] Parameterized Complexity of Secluded Connectivity Problems
    Fedor V. Fomin
    Petr A. Golovach
    Nikolay Karpov
    Alexander S. Kulikov
    Theory of Computing Systems, 2017, 61 : 795 - 819
  • [3] On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs
    Jiang, Minghui
    COMBINATORIAL PATTERN MATCHING, PROCEEDINGS, 2010, 6129 : 125 - 137
  • [4] On the parameterized complexity of some optimization problems related to multiple-interval graphs
    Jiang, Minghui
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (49) : 4253 - 4262
  • [5] Parameterized Complexity for Domination Problems on Degenerate Graphs
    Golovach, Petr A.
    Villanger, Yngve
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2008, 5344 : 195 - 205
  • [6] Parameterized complexity of cardinality constrained optimization problems
    Cai, Leizhen
    COMPUTER JOURNAL, 2008, 51 (01): : 102 - 121
  • [7] Parameterized complexity of cardinality constrained optimization problems
    Cai, Leizhen
    Computer Journal, 2008, 51 (01): : 102 - 121
  • [8] On the complexity of some colorful problems parameterized by treewidth
    Fellows, Michael R.
    Fomin, Fedor V.
    Lokshtanov, Daniel
    Rosamond, Frances
    Saurabh, Saket
    Szeider, Stefan
    Thomassen, Carsten
    INFORMATION AND COMPUTATION, 2011, 209 (02) : 143 - 153
  • [9] The parameterized complexity of some minimum label problems
    Fellows, Michael R.
    Guo, Jiong
    Kanj, Iyad
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2010, 76 (08) : 727 - 740
  • [10] On the complexity of some colorful problems parameterized by treewidth
    Fellows, Michael
    Fornin, Fedor V.
    Lokshtanov, Daniel
    Rosamond, Frances
    Saurabh, Saket
    Szeider, Stefan
    Thomassen, Carsten
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2007, 4616 : 366 - +
12345