Maximum matching and kernelization of edge dominating set

DOI10.1016/J.IPL.2018.03.019MaRDI QIDQ1751411zbMATH OpenOpenAlexFDO

Authors 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 problemsedge dominating setkernelizationmaximum matchingparameterized algorithm

Mathematics Subject Classification ID

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

Recommendations

• On kernelization for edge dominating set under structural parameters
• Maximal matching and edge domination in complete multipartite graphs
• Algorithms and Computation
• scientific article; zbMATH DE number 866672
• On the maximum edge-pair embedding bipartite matching
• On the maximum edge-pair embedding bipartite matching
• Kernels for edge dominating set: simpler or smaller
• Maximum matching width: new characterizations and a fast algorithm for dominating set
• Maximum matching width: new characterizations and a fast algorithm for dominating set
• Maximum weight edge-constrained matchings

Cites work

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

Cited in

(5)

• 2-(edge-)connected edge domination number and matching number
• Kernels for edge dominating set: simpler or smaller
• scientific article; zbMATH DE number 866672 (Why is no real title available?)
• On kernelization for edge dominating set under structural parameters
• SOFSEM 2006: Theory and Practice of Computer Science

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751411)