Maximum Matching in almost linear time on graphs of bounded clique-width

DOI10.4230/LIPICS.IPEC.2021.15MaRDI QIDQ6192483zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe

Publication date 12 February 2024

Full work available at URL https://hal.science/hal-03445479

zbMATH Keywords

clique-widthCourcelle's theoremFPT in Pmaximum \(b\)-matchingmaximum matchingtree-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• Maximum matching in almost linear time on graphs of bounded clique-width
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• scientific article; zbMATH DE number 6850484
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• The \(b\)-matching problem in distance-hereditary graphs and beyond

Cited in

(3)

• Maximum matching in almost linear time on graphs of bounded clique-width
• The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
• The \(b\)-matching problem in distance-hereditary graphs and beyond

This page was built for publication: Maximum Matching in almost linear time on graphs of bounded clique-width

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