Disconnected matchings

DOI10.1016/J.TCS.2023.113821MaRDI QIDQ5972267zbMATH OpenOpenAlexFDO

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

Publication date 26 April 2023

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

Full work available at URL https://doi.org/10.1016/j.tcs.2023.113821

zbMATH Keywords

algorithmscomplexityinduced subgraphsmatchings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Disconnected matchings
• scientific article; zbMATH DE number 1953189
• Connected matchings in chordal bipartite graphs
• scientific article; zbMATH DE number 19225

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Acyclic Matching in Some Subclasses of Graphs
• Cross-composition: a new technique for kernelization lower bounds
• Degenerate matchings and edge colorings
• Editing graphs to satisfy degree constraints: a parameterized approach
• Efficient enumeration of all minimal separators in a graph
• 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
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953189 (Why is no real title available?)
• scientific article; zbMATH DE number 1796975 (Why is no real title available?)
• Induced matchings
• Maximum matchings and trees
• On maximum induced matchings in bipartite graphs
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Parameterized algorithms
• Parameterized algorithms and kernels for almost induced matching
• Parameterized complexity of finding regular induced subgraphs
• Paths, Trees, and Flowers
• The complexity of satisfiability problems
• The parameterized complexity of the induced matching problem
• Uniquely restricted matchings

Cited in

(11)

• Relating dissociation, independence, and matchings
• Disconnected matchings
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• On the complexity of minimum maximal acyclic matchings
• Polyhedral approach to weighted connected matchings in general graphs
• Parameterized results on acyclic matchings with implications for related problems
• Complexity of deciding the equality of matching numbers
• Parameterized complexity of disconnected matchings
• \(\mathcal{P}\)-matchings parameterized by treewidth
• Weighted connected matchings
• Structural parameterizations for induced and acyclic matching

This page was built for publication: Disconnected matchings

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