Structural parameterizations for induced and acyclic matching

Cites work

$\mathcal{P}$-matchings parameterized by treewidth
$\mathcal{P}$-matchings Parameterized by Treewidth
A note on the NP-hardness of two matching problems in induced subgrids
A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
Acyclic matching in some subclasses of graphs
Acyclic matchings in graphs of bounded maximum degree
Acyclic matchings in subclasses of bipartite graphs
Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
Approximability results for the maximum and minimum maximal induced matching problems
Approximating weighted induced matchings
Approximation hardness of dominating set problems in bounded degree graphs
Bipartite Domination and Simultaneous Matroid Covers
Complexity of approximating bounded variants of optimization problems
Degenerate matchings and edge colorings
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Disconnected matchings
Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
Exact algorithms for maximum induced matching
Exact and approximate bandwidth
Fast exact algorithms for some connectivity problems parameterized by clique-width
Faster algorithms on branch and clique decompositions
Finding a maximum induced matching in weakly chordal graphs
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
Finer tight bounds for coloring on clique-width
Generalized subgraph-restricted matchings in graphs
Graph products revisited: tight approximation hardness of induced matching, poset dimension and more
Graph theory
scientific article; zbMATH DE number 3709576 (Why is no real title available?)
scientific article; zbMATH DE number 1420901 (Why is no real title available?)
Title not available (Why is no real title available?)
Improved induced matchings in sparse graphs
Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses
Induced matching below guarantees: average paves the way for fixed-parameter tractability
Induced matchings
Induced matchings in asteroidal triple-free graphs
Linear programming based approximation for unweighted induced matchings -- breaking the $\varDelta$ barrier
Linear time solvable optimization problems on graphs of bounded clique-width
Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
Locally searching for large induced matchings
Matching theory
Maximum induced matching algorithms via vertex ordering characterizations
Maximum induced matching problem on hhd-free graphs
Maximum induced matchings for chordal graphs in linear time
Moderately exponential time algorithms for the maximum induced matching problem
New results on induced matchings
New results on maximum induced matchings in bipartite graphs and beyond
NP-completeness of some generalizations of the maximum matching problem
On maximum induced matchings in bipartite graphs
On problems as hard as CNF-SAT
On some hard and some tractable cases of the maximum acyclic matching problem
On the approximability of the maximum feasible subsystem problem with 0/1-coefficients
On the approximability of the maximum induced matching problem
On the induced matching problem
On the parameterized complexity of the acyclic matching problem
Parameterized algorithms
Parameterized algorithms and kernels for almost induced matching
Parameterized complexity of finding regular induced subgraphs
Parameterized results on acyclic matchings with implications for related problems
Structural parameterizations for two bounded degree problems revisited
The induced matching and chain subgraph cover problems for convex bipartite graphs
The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
The parameterized complexity of the induced matching problem
Tight algorithms for connectivity problems parameterized by clique-width
Two greedy consequences for maximum induced matchings
Upper bounds to the clique width of graphs

This page was built for publication: Structural parameterizations for induced and acyclic matching

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