Parameterized complexity of perfectly matched sets

DOI10.1016/J.TCS.2023.113861OpenAlexW4362663715MaRDI QIDQ6038698FDOQ6038698

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

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
• scientific article; zbMATH DE number 7561679
• 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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (5)

• Parameterized complexity of conflict-free matchings and paths
• Computational complexity of simultaneous elementary matching problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of irredundant sets parameterized by size

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)