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 problemskernelizationmaximum matchingparameterized algorithmedge dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) 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) Parameterized complexity, tractability and kernelization (68Q27)

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 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
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(4)

• SOFSEM 2006: Theory and Practice of Computer Science
• On kernelization for edge dominating set under structural parameters
• 2-(edge-)connected edge domination number and matching number
• Kernels for edge dominating set: simpler or smaller

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)