Perfectly matched sets in graphs: parameterized and exact computation

DOI10.1016/J.TCS.2023.113797MaRDI QIDQ2697539zbMATH OpenOpenAlexFDO

Authors N. R. Aravind, Roopam Saxena

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

algorithmsfixed parameter tractableperfect matchingperfectly matched sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Parameterized complexity of perfectly matched sets
• The perfect matching cut problem revisited
• The complexity of the perfect matching-cut problem
• On the parameterized vertex cover problem for graphs with perfect matching
• The parameterized complexity of the induced matching problem

Cites work

• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• A fast branching algorithm for cluster vertex deletion
• Algorithms solving the matching cut problem
• Approximating clique-width and branch-width
• Bipartite Domination and Simultaneous Matroid Covers
• Cross-composition: a new technique for kernelization lower bounds
• Exact algorithms for maximum induced matching
• Finding a maximum induced matching in weakly chordal graphs
• Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization
• 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
• Fundamentals of parameterized complexity
• Graph minors. III. Planar tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Improved induced matchings in sparse graphs
• Induced matchings
• Induced matchings in intersection graphs.
• Kernel bounds for disjoint cycles and disjoint paths
• Linear time solvable optimization problems on graphs of bounded clique-width
• Matching cut in graphs with large minimum degree
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• New results on induced matchings
• NP-completeness of some generalizations of the maximum matching problem
• On maximum induced matchings in bipartite graphs
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• On structural parameterizations of the matching cut problem
• On the complexity of matching cut in graphs of fixed diameter
• On the induced matching problem
• Parameterized algorithms
• Recognizing decomposable graphs
• The complexity of irredundant sets parameterized by size
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The parameterized complexity of the induced matching problem
• Treewidth. Computations and approximations
• Upper bounds to the clique width of graphs

Cited in

(2)

• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• Parameterized complexity of perfectly matched sets

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

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