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 条
  • [31] On the fixed-parameter tractability of the equivalence test of monotone normal forms
    Hagen, Matthias
    INFORMATION PROCESSING LETTERS, 2007, 103 (04) : 163 - 167
  • [32] Fixed-parameter tractability of graph modification problems for hereditary properties
    Cai, LZ
    INFORMATION PROCESSING LETTERS, 1996, 58 (04) : 171 - 176
  • [33] FIXED-PARAMETER TRACTABILITY OF DIRECTED MULTIWAY CUT PARAMETERIZED BY THE SIZE OF THE CUTSET
    Chitnis, Rajesh
    Hajiaghayi, Mohammadtaghi
    Marx, Daniel
    SIAM JOURNAL ON COMPUTING, 2013, 42 (04) : 1674 - 1696
  • [34] Geometric Clustering: Fixed-Parameter Tractability and Lower Bounds with Respect to the Dimension
    Cabello, Sergio
    Giannopoulos, Panos
    Knauer, Christian
    Marx, Daniel
    Rote, Guenter
    ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (04)
  • [35] Fixed-Parameter Tractability of Counting Small Minimum (S, T)-Cuts
    Berge, Pierre
    Mouscadet, Benjamin
    Rimmel, Arpad
    Tomasik, Joanna
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019), 2019, 11789 : 79 - 92
  • [36] Fixed-parameter algorithms for the cocoloring problem
    Campos, Victor
    Klein, Sulamita
    Sampaio, Rudini
    Silva, Ana
    DISCRETE APPLIED MATHEMATICS, 2014, 167 : 52 - 60
  • [37] Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability
    Buchin, Kevin
    Buchin, Maike
    Byrka, Jaroslaw
    Noellenburg, Martin
    Okamoto, Yoshio
    Silveira, Rodrigo I.
    Wolff, Alexander
    ALGORITHMICA, 2012, 62 (1-2) : 309 - 332
  • [38] Geometric Clustering: Fixed-Parameter Tractability and Lower Bounds with Respect to the Dimension
    Cabello, Sergio
    Giannopoulos, Panos
    Knauer, Christian
    Rote, Guenter
    PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2008, : 836 - +
  • [39] FIXED-PARAMETER ALGORITHMS FOR MAXIMUM AGREEMENT FORESTS
    Whidden, Chris
    Beiko, Robert G.
    Zeh, Norbert
    SIAM JOURNAL ON COMPUTING, 2013, 42 (04) : 1431 - 1466
  • [40] Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability
    Yongjie Yang
    Jianxin Wang
    Autonomous Agents and Multi-Agent Systems, 2023, 37
12345