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 条
  • [21] A Bisection Approach to Subcubic Maximum Induced Matching
    Hoi, Gordon
    Jain, Sanjay
    Sabili, Ammar Fathin
    Stephan, Frank
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024, 2024, 14549 : 257 - 272
  • [22] New exact algorithms for planar maximum covering location by ellipses problems
    Tedeschi, Danilo
    Andretta, Marina
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 291 (01) : 114 - 127
  • [23] Exact algorithms for dominating set
    van Rooij, Johan M. M.
    Bodlaender, Hans L.
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (17) : 2147 - 2164
  • [24] Dominating set based exact algorithms for 3-coloring
    Narayanaswamy, N. S.
    Subramanian, C. R.
    INFORMATION PROCESSING LETTERS, 2011, 111 (06) : 251 - 255
  • [25] Exact Algorithms for Maximum Lifetime Data-Gathering Tree in Wireless Sensor Networks
    Casazza, Marco
    Ceselli, Alberto
    INFORMS JOURNAL ON COMPUTING, 2022, 34 (04) : 1987 - 2002
  • [26] Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms
    Komusiewicz, Christian
    Kratsch, Dieter
    Le, Van Bang
    DISCRETE APPLIED MATHEMATICS, 2020, 283 (44-58) : 44 - 58
  • [27] Approximability results for the maximum and minimum maximal induced matching problems
    Orlovich, Yury
    Finke, Gerd
    Gordon, Valery
    Zverovich, Igor
    DISCRETE OPTIMIZATION, 2008, 5 (03) : 584 - 593
  • [28] Exact Algorithms for Intervalizing Coloured Graphs
    Bodlaender, Hans L.
    van Rooij, Johan M. M.
    THEORY OF COMPUTING SYSTEMS, 2016, 58 (02) : 273 - 286
  • [29] Exact Algorithms for Intervalizing Coloured Graphs
    Hans L. Bodlaender
    Johan M. M. van Rooij
    Theory of Computing Systems, 2016, 58 : 273 - 286
  • [30] An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation
    Konrad, Christian
    Naidu, Kheeran K.
    PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2024, : 2881 - 2899
12345