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 条
  • [31] A simple reduction from maximum weight matching to maximum cardinality matching
    Pettie, S.
    INFORMATION PROCESSING LETTERS, 2012, 112 (23) : 893 - 898
  • [32] Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
    Xiao, Mingyu
    Kou, Shaowei
    THEORETICAL COMPUTER SCIENCE, 2017, 657 : 86 - 97
  • [33] PARAMETERIZED EXACT AND APPROXIMATION ALGORITHMS FOR MAXIMUM k-SET COVER AND RELATED SATISFIABILITY PROBLEMS
    Bonnet, Edouard
    Paschos, Vangelis Th.
    Sikora, Florian
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2016, 50 (03): : 227 - 240
  • [34] Parameterized and exact algorithms for class domination coloring
    Krithika, R.
    Rai, Ashutosh
    Saurabh, Saket
    Tale, Prafullkumar
    DISCRETE APPLIED MATHEMATICS, 2021, 291 : 286 - 299
  • [35] Sort and Search: Exact algorithms for generalized domination
    Fomin, Fedor V.
    Golovach, Petr A.
    Kratochvil, Jan
    Kratsch, Dieter
    Liedloff, Mathieu
    INFORMATION PROCESSING LETTERS, 2009, 109 (14) : 795 - 798
  • [36] A dynamic programming algorithm for the maximum induced matching problem in permutation graphs
    Viet-Dung Nguyen
    Ba-Thai Pham
    Viet-Hung Tran
    Phan-Thuan Do
    PROCEEDINGS OF THE NINTH INTERNATIONAL SYMPOSIUM ON INFORMATION AND COMMUNICATION TECHNOLOGY (SOICT 2018), 2018, : 92 - 97
  • [37] Quadratic time algorithm for maximum induced matching problem in trapezoid graphs
    Viet-Dung Nguyen
    Phan-Thuan Do
    PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON INFORMATION SCIENCE AND SYSTEMS (ICISS 2019), 2019, : 185 - 189
  • [38] Parameterized and Exact Algorithms for Class Domination Coloring
    Krithika, R.
    Rai, Ashutosh
    Saurabh, Saket
    Tale, Prafullkumar
    SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2017, 10139 : 336 - 349
  • [39] NK-MaxClique and MMCQ: Tow New Exact Branch and Bound Algorithms for the Maximum Clique Problem
    Mohammadi, Neda
    Kadivar, Mehdi
    IEEE ACCESS, 2020, 8 (180045-180053) : 180045 - 180053
  • [40] Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
    Andreas Björklund
    Thore Husfeldt
    Algorithmica, 2008, 52 : 226 - 249
12345