Maximum matching and kernelization of edge dominating set

DOI10.1016/j.ipl.2018.03.019zbMath1457.68216OpenAlexW2794851078MaRDI QIDQ1751411

Hang Gao, Wenyu Gao

Publication date: 25 May 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.03.019

zbMATH Keywords

combinatorial problemsmaximum matchingkernelizationparameterized algorithmedge dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

2-(edge-)connected edge domination number and matching number

Cites Work

• Planar graph vertex partition for linear problem kernels
• Parameterized edge dominating set in graphs with degree bounded by 3
• New parameterized algorithms for the edge dominating set problem
• On two techniques of combining branching and treewidth
• A fixed-parameter tractable algorithm for matrix domination
• Kernels for Edge Dominating Set: Simpler or Smaller
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• On the Number of Disjoint Edges in a Graph
• Edge Dominating Sets in Graphs

This page was built for publication: Maximum matching and kernelization of edge dominating set