Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters

被引：0
|
作者：
Kucera, Martin [1 ]
Suchy, Ondrej [1 ]
机构：
[1] Czech Tech Univ, Dept Theoret Comp Sci, Fac Informat Technol, Thakurova 9, Prague 16000, Czech Republic
来源：
ALGORITHMICA | 2023年 / 85卷 / 03期
关键词：
Graph theory; Minimum eccentricity shortest path; Parameterized complexity; Fixed-parameter tractable;
D O I：
10.1007/s00453-022-01006-x
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt-algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of treewidth with the desired eccentricity, and maximum leaf number.
引用
收藏
页码：762 / 782
页数：21
相关论文
共 50 条
  • [1] Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
    Martin Kučera
    Ondřej Suchý
    Algorithmica, 2023, 85 : 762 - 782
  • [2] Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
    Kucera, Martin
    Suchy, Ondrej
    COMBINATORIAL ALGORITHMS, IWOCA 2021, 2021, 12757 : 442 - 455
  • [3] On the minimum eccentricity shortest path problem
    Dragan, Feodor F.
    Leitert, Arne
    THEORETICAL COMPUTER SCIENCE, 2017, 694 : 66 - 78
  • [4] Parameterized Algorithms for Eccentricity Shortest Path Problem
    Bhyravarapu, Sriram
    Jana, Satyabrata
    Kanesh, Lawqueen
    Saurabh, Saket
    Verma, Shaily
    COMBINATORIAL ALGORITHMS, IWOCA 2023, 2023, 13889 : 74 - 86
  • [5] THE MINIMUM-COVERING SHORTEST-PATH PROBLEM
    CURRENT, J
    REVELLE, C
    COHON, J
    DECISION SCIENCES, 1988, 19 (03) : 490 - 503
  • [6] The shortest path problem on networks with fuzzy parameters
    Hernandes, Fabio
    Lamata, Maria Teresa
    Verdegay, Jose Luis
    Yamakami, Akebo
    FUZZY SETS AND SYSTEMS, 2007, 158 (14) : 1561 - 1570
  • [7] On the approximability of the minimum congestion unsplittable shortest path routing problem
    Bley, A
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2005, 3509 : 97 - 110
  • [8] Shortest conditional decreasing path algorithm for the parametric minimum flow problem
    Ciurea, Eleonor
    Parpalea, Mircea
    BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE, 2013, 56 (04): : 387 - 401
  • [9] The Restricted Minimum Single Source Shortest Path Tree Expansion Problem
    Wang, Haiyan
    Deng, Weiqi
    Huang, Binchao
    Li, Jianping
    2017 16TH IEEE/ACIS INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCE (ICIS 2017), 2017, : 63 - 68
  • [10] A Shortest Path Problem
    JIA Zhengsheng(Mathematics and Mechanics Department of Taiyuan University of technology Taiyuan 030024)FAN Hui(Foundation Department Shan Xi Mining Industry institute
    JournalofSystemsScienceandSystemsEngineering, 1996, (04) : 496 - 499
12345