Parameterized complexity of perfectly matched sets

DOI10.1016/J.TCS.2023.113861MaRDI QIDQ6038698zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Sutanay Bhattacharjee, Satyabrata Jana, Abhishek Sahu

Publication date 2 May 2023

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

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

zbMATH Keywords

interval graphsparameterized complexityplanar graphs\(d\)-degenerate graphsapex-minor-free graphsperfectly matched sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Perfectly matched sets in graphs: parameterized and exact computation
• The parameterized complexity of the induced matching problem
• On the parameterized complexity of the acyclic matching problem
• Parameterized complexity of conflict-free matchings and paths
• Parameterized complexity of conflict-free matchings and paths
• scientific article; zbMATH DE number 3921983
• Complexity of matching problems
• Tight lower bounds on the resolution complexity of perfect matching principles
• Sublinear Algorithms for Parameterized Matching
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Extremal combinatorics. With applications in computer science
• Graph theory
• Improved induced matchings in sparse graphs
• Induced matchings in intersection graphs.
• Interval deletion is fixed-parameter tractable
• Interval graph representation with given interval and intersection lengths
• Matching cut in graphs with large minimum degree
• Matching cutsets in graphs
• NP-completeness of some generalizations of the maximum matching problem
• New results on maximum induced matchings in bipartite graphs and beyond
• On the complexity of matching cut in graphs of fixed diameter
• On the induced matching problem
• On the np-completeness of certain network testing problems
• Parameterized algorithms
• Parametrized complexity theory.
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Recognizing decomposable graphs
• Subexponential algorithms for partial cover problems
• The Bidimensional Theory of Bounded-Genus Graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The parameterized complexity of the induced matching problem
• The perfect matching cut problem revisited
• Uniquely restricted matchings in interval graphs

Cited in

(6)

• Parameterized complexity of conflict-free matchings and paths
• Computational complexity of simultaneous elementary matching problems
• Perfectly matched sets in graphs: parameterized and exact computation
• The complexity of irredundant sets parameterized by size
• scientific article; zbMATH DE number 4049047 (Why is no real title available?)
• scientific article; zbMATH DE number 549852 (Why is no real title available?)

This page was built for publication: Parameterized complexity of perfectly matched sets

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