Parameterized complexity of perfectly matched sets

DOI10.1016/j.tcs.2023.113861OpenAlexW4362663715MaRDI QIDQ6038698

Satyabrata Jana, Abhishek Sahu, Sutanay Bhattacharjee, Akanksha Agrawal

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

planar graphsinterval graphsparameterized complexity\(d\)-degenerate graphsapex-minor-free graphsperfectly matched sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graph representation with given interval and intersection lengths
• Improved induced matchings in sparse graphs
• On the induced matching problem
• The parameterized complexity of the induced matching problem
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings in intersection graphs.
• Subexponential algorithms for partial cover problems
• New results on maximum induced matchings in bipartite graphs and beyond
• Parametrized complexity theory.
• Graph Theory
• Extremal Combinatorics
• Uniquely Restricted Matchings in Interval Graphs
• On the np-completeness of certain network testing problems
• Recognizing decomposable graphs
• The Bidimensional Theory of Bounded-Genus Graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Interval Deletion Is Fixed-Parameter Tractable
• Matching cutsets in graphs
• Parameterized Algorithms
• Matching cut in graphs with large minimum degree
• The perfect matching cut problem revisited

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