The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability

被引：0
|
作者：
Mkrtchyan V. [1 ]
机构：
[1] Gran Sasso Science Institute, School of Advanced Studies, L’Aquila
来源：
Journal of Graph Algorithms and Applications | 2024年 / 28卷 / 01期
关键词：
Edge-coloring; exact algorithm; fixed-parameter tractability; maximum 2-edge-colorable subgraph;
D O I：
10.7155/jgaa.v28i1.2931
中图分类号：
学科分类号：
摘要：
A k-edge-coloring of a graph is an assignment of colors {1, …, k} to edges of the graph such that adjacent edges receive different colors. In the maximum k-edge-colorable subgraph problem we are given a graph and an integer k, the goal is to find a k-edge-colorable subgraph with maximum number of edges together with its k-edge-coloring. In this paper, we consider the maximum 2-edge-colorable subgraph problem and present some results that deal with the fixed-parameter tractability of this problem. © 2024, Brown University. All rights reserved.
引用
收藏
页码：129 / 147
页数：18
相关论文
共 50 条
  • [41] Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability
    Yang, Yongjie
    Wang, Jianxin
    AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 2023, 37 (02)
  • [42] An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
    Abu-Khzam, Faisal N.
    Makarem, Norma
    Shehab, Maryam
    THEORETICAL COMPUTER SCIENCE, 2023, 958
  • [43] Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
    Stefan Kratsch
    Frank Neumann
    Algorithmica, 2013, 65 : 754 - 771
  • [44] Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
    Kratsch, Stefan
    Neumann, Frank
    ALGORITHMICA, 2013, 65 (04) : 754 - 771
  • [45] Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
    You, Jie
    Shi, Feng
    Wang, Jianxin
    Feng, Qilong
    THEORETICAL COMPUTER SCIENCE, 2020, 806 : 256 - 270
  • [46] Improving a fixed parameter tractability time bound for the shadow problem
    Heusch, P
    Porschen, S
    Speckenmeyer, E
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) : 772 - 788
  • [47] Fixed parameter tractability of a biconnected bottleneck Steiner network problem
    Ras, Charl J.
    NETWORKS, 2020, 75 (03) : 310 - 320
  • [48] A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem
    Bansal, Mukul S.
    Shamir, Ron
    IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2011, 8 (03) : 848 - 850
  • [49] Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees
    Whidden, Chris
    Beiko, Robert G.
    Zeh, Norbert
    ALGORITHMICA, 2016, 74 (03) : 1019 - 1054
  • [50] Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees
    Chris Whidden
    Robert G. Beiko
    Norbert Zeh
    Algorithmica, 2016, 74 : 1019 - 1054
12345