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 条
  • [1] Scheduling and fixed-parameter tractability
    Mnich, Matthias
    Wiese, Andreas
    MATHEMATICAL PROGRAMMING, 2015, 154 (1-2) : 533 - 562
  • [2] On disjoint matchings in cubic graphs: Maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs
    Aslanyan, Davit
    Mkrtchyan, Vahan V.
    Petrosyan, Samvel S.
    Vardanyan, Gagik N.
    DISCRETE APPLIED MATHEMATICS, 2014, 172 : 12 - 27
  • [3] Scheduling and fixed-parameter tractability
    Matthias Mnich
    Andreas Wiese
    Mathematical Programming, 2015, 154 : 533 - 562
  • [4] Approximating the maximum 3-edge-colorable subgraph problem
    Rizzi, Romeo
    DISCRETE MATHEMATICS, 2009, 309 (12) : 4166 - 4170
  • [5] Finding a maximum minimal separator: Graph classes and fixed-parameter tractability
    Hanaka, Tesshu
    Kobayashi, Yasuaki
    Kobayashi, Yusuke
    Yagita, Tsuyoshi
    THEORETICAL COMPUTER SCIENCE, 2021, 865 : 131 - 140
  • [6] Minimizing Movement: Fixed-Parameter Tractability
    Demaine, Erik D.
    Hajiaghayi, Mohammadtaghi
    Marx, Daniel
    ACM TRANSACTIONS ON ALGORITHMS, 2014, 11 (02) : 1 - 29
  • [7] Parameterized Complexity of MAXIMUM EDGE COLORABLE SUBGRAPH
    Agrawal, Akanksha
    Kundu, Madhumita
    Sahu, Abhishek
    Saurabh, Saket
    Tale, Prafullkumar
    COMPUTING AND COMBINATORICS (COCOON 2020), 2020, 12273 : 615 - 626
  • [8] Parameterized Complexity of Maximum Edge Colorable Subgraph
    Agrawal, Akanksha
    Kundu, Madhumita
    Sahu, Abhishek
    Saurabh, Saket
    Tale, Prafullkumar
    ALGORITHMICA, 2022, 84 (10) : 3075 - 3100
  • [9] Parameterized Complexity of Maximum Edge Colorable Subgraph
    Akanksha Agrawal
    Madhumita Kundu
    Abhishek Sahu
    Saket Saurabh
    Prafullkumar Tale
    Algorithmica, 2022, 84 : 3075 - 3100
  • [10] On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
    Mkrtchyan V.
    Petrosyan G.
    Journal of Graph Algorithms and Applications, 2022, 26 (01) : 91 - 110
12345