Weighted connected matchings

DOI10.1016/J.TCS.2025.115149MaRDI QIDQ7006267zbMATH OpenFDO

Authors Guilherme C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Vinícius F. dos Santos, Jayme L. Szwarcfiter

Publication date 31 March 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115149

zbMATH Keywords

complexitygraph algorithmsinduced subgraphsmatchings

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953189 (Why is no real title available?)
• Acyclic matching in some subclasses of graphs
• Cross-composition: a new technique for kernelization lower bounds
• Degenerate matchings and edge colorings
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Disconnected matchings
• Disconnected matchings
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Generalized subgraph-restricted matchings in graphs
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Graph theory
• Induced matching below guarantees: average paves the way for fixed-parameter tractability
• Induced matchings
• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
• Maximum matching and a polyhedron with 0,1-vertices
• Maximum weight induced matching in some subclasses of bipartite graphs
• Minimum maximal acyclic matching in proper interval graphs
• On maximum induced matchings in bipartite graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• On the complexity of minimum maximal acyclic matchings
• On the parameterized complexity of the acyclic matching problem
• Parameterized algorithms
• Parameterized results on acyclic matchings with implications for related problems
• Paths, Trees, and Flowers
• Planar Formulae and Their Uses
• Reducibility among combinatorial problems
• Scaling algorithms for weighted matching in general graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• The parameterized complexity of the induced matching problem
• Uniquely restricted matchings
• Weighted connected matchings

This page was built for publication: Weighted connected matchings

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