Exact algorithms for Maximum Induced Matching

被引：13
|
作者：
Xiao, Mingyu [1 ]
Tan, Huan [2 ]
机构：
[1] Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Chengdu 611731, Sichuan, Peoples R China
[2] Univ Elect Sci & Technol China, Chengdu 611731, Sichuan, Peoples R China
来源：
INFORMATION AND COMPUTATION | 2017年 / 256卷
基金：
中国国家自然科学基金;
关键词：
Exact algorithms; Graph algorithms; Maximum induced matching; APPROXIMABILITY; COMPLEXITY; SET;
D O I：
10.1016/j.ic.2017.07.006
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper studies exact algorithms for the MAXIMUM INDUCED MATCHING problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in O*(1.4231(n)) time and polynomial space or O*(1.3752(n)) time and exponential space. (C) 2017 Elsevier Inc. All rights reserved.
引用
收藏
页码：196 / 211
页数：16
相关论文
共 50 条
  • [1] An Improved Exact Algorithm for Maximum Induced Matching
    Xiao, Mingyu
    Tan, Huan
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015), 2015, 9076 : 272 - 283
  • [2] Exact algorithms for dominating induced matching based on graph partition
    Xiao, Mingyu
    Nagamochi, Hiroshi
    DISCRETE APPLIED MATHEMATICS, 2015, 190 : 147 - 162
  • [3] Moderately exponential time algorithms for the maximum induced matching problem
    Chang, Maw-Shang
    Chen, Li-Hsuan
    Hung, Ling-Ju
    OPTIMIZATION LETTERS, 2015, 9 (05) : 981 - 998
  • [4] Exact Algorithms for Minimum Weighted Dominating Induced Matching
    Min Chih Lin
    Michel J. Mizrahi
    Jayme L. Szwarcfiter
    Algorithmica, 2017, 77 : 642 - 660
  • [5] Exact Algorithms for Minimum Weighted Dominating Induced Matching
    Lin, Min Chih
    Mizrahi, Michel J.
    Szwarcfiter, Jayme L.
    ALGORITHMICA, 2017, 77 (03) : 642 - 660
  • [6] Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
    Habib, Michel
    Mouatadid, Lalla
    ALGORITHMICA, 2020, 82 (02) : 260 - 278
  • [7] Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
    Michel Habib
    Lalla Mouatadid
    Algorithmica, 2020, 82 : 260 - 278
  • [8] Parameterized algorithms and kernels for almost induced matching
    Xiao, Mingyu
    Kou, Shaowei
    THEORETICAL COMPUTER SCIENCE, 2020, 846 : 103 - 113
  • [9] Exact Algorithms for Maximum Clique: A Computational Study
    Prosser, Patrick
    ALGORITHMS, 2012, 5 (04) : 545 - 587
  • [10] Exact Algorithms for Maximum Weighted Independent Set on Sparse Graphs (Extended Abstract)
    Huang, Sen
    Xiao, Mingyu
    Chen, Xiaoyu
    COMPUTING AND COMBINATORICS (COCOON 2021), 2021, 13025 : 617 - 628
12345