DROPS - Document
DROPS - Document License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0) When quoting this document, please refer to the following DOI: 10.4230/LIPIcs.ISAAC.2018.30 URN: urn:nbn:de:0030-drops-99783 URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9978/ Go to the corresponding LIPIcs Volume Portal Ducoffe, Guillaume ; Popa, Alexandru The b-Matching Problem in Distance-Hereditary Graphs and Beyond pdf-format: LIPIcs-ISAAC-2018-30.pdf (0.5 MB) Abstract We make progress on the fine-grained complexity of Maximum-Cardinality Matching on graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been recently proposed for the important subclasses of bounded-treewidth graphs (Fomin et al., SODA'17) and graphs of bounded modular-width (Coudert et al., SODA'18).
OPUS