Exact algorithms for Maximum Induced Matching

被引：14
|
作者：
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 条
  • [41] Exact algorithms for exact satisfiability and number of perfect matchings
    Bjorklund, Andreas
    Husfeldt, Thore
    ALGORITHMICA, 2008, 52 (02) : 226 - 249
  • [42] An improved kernel and parameterized algorithm for deletion to induced matching
    Liu, Yuxi
    Xiao, Mingyu
    THEORETICAL COMPUTER SCIENCE, 2025, 1041
  • [43] On exact algorithms for the permutation CSP
    Kim, Eun Jung
    Goncalves, Daniel
    THEORETICAL COMPUTER SCIENCE, 2013, 511 : 109 - 116
  • [44] Exact Algorithms for Edge Domination
    van Rooij, Johan M. M.
    Bodlaender, Hans L.
    ALGORITHMICA, 2012, 64 (04) : 535 - 563
  • [45] Iterative compression and exact algorithms
    Fomin, Fedor V.
    Gaspers, Serge
    Kratsch, Dieter
    Liedloff, Mathieu
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (7-9) : 1045 - 1053
  • [46] Exact Algorithms for Edge Domination
    Johan M. M. van Rooij
    Hans L. Bodlaender
    Algorithmica, 2012, 64 : 535 - 563
  • [47] Exact Algorithms for Terrain Guarding
    Ashok, Pradeesha
    Fomin, Fedor, V
    Kolay, Sudeshna
    Saurabh, Saket
    Zehavi, Meirav
    ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (02)
  • [48] Exact algorithms for edge domination
    van Rooij, Johan M. M.
    Bodlaender, Hans L.
    PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 2008, 5018 : 214 - 225
  • [49] Optimal pattern matching algorithms
    Didier, Gilles
    JOURNAL OF COMPLEXITY, 2019, 51 : 79 - 109
  • [50] New results on maximum induced matchings in bipartite graphs and beyond
    Dabrowski, Konrad K.
    Demange, Marc
    Lozin, Vadim V.
    THEORETICAL COMPUTER SCIENCE, 2013, 478 : 33 - 40
12345