Perfectly matched sets in graphs: parameterized and exact computation

DOI10.1016/j.tcs.2023.113797OpenAlexW4323276281MaRDI QIDQ2697539

Roopam Saxena, N. R. Aravind

Publication date: 12 April 2023

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

Full work available at URL: https://arxiv.org/abs/2107.08584

zbMATH Keywords

algorithmsperfect matchingfixed parameter tractableperfectly matched sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast branching algorithm for cluster vertex deletion
• Fundamentals of parameterized complexity
• Improved induced matchings in sparse graphs
• Kernel bounds for disjoint cycles and disjoint paths
• On the induced matching problem
• Graph minors. III. Planar tree-width
• Algorithms solving the matching cut problem
• The parameterized complexity of the induced matching problem
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Treewidth. Computations and approximations
• Induced matchings in intersection graphs.
• On structural parameterizations of the matching cut problem
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• 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
• Finding a maximum induced matching in weakly chordal graphs
• On maximum induced matchings in bipartite graphs
• The complexity of irredundant sets parameterized by size
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• New results on induced matchings
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Exact algorithms for maximum induced matching
• Approximating clique-width and branch-width
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Bipartite Domination and Simultaneous Matroid Covers
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Parameterized Algorithms
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• Matching cut in graphs with large minimum degree

This page was built for publication: Perfectly matched sets in graphs: parameterized and exact computation