NP-completeness of some generalizations of the maximum matching problem
From MaRDI portal
Publication:1168728
DOI10.1016/0020-0190(82)90077-1zbMath0493.68039OpenAlexW2068155033WikidataQ130492490 ScholiaQ130492490MaRDI QIDQ1168728
Larry J. Stockmeyer, Vijay V. Vazirani
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90077-1
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (93)
On the computational complexity of the Helly number in the \(P_3\) and related convexities ⋮ A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ Acyclic matchings in graphs of bounded maximum degree ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ On graphs with induced matching number almost equal to matching number ⋮ A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graphs with maximal induced matchings of the same size ⋮ A characterization of well-indumatchable graphs having girth greater than seven ⋮ A PTAS for the sparsest 2-spanner of 4-connected planar triangulations ⋮ Exact algorithms for maximum induced matching ⋮ Improved induced matchings in sparse graphs ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ Induced matchings in subcubic graphs without short cycles ⋮ Parameterized complexity of perfectly matched sets ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Computational complexity aspects of super domination ⋮ Maximum Induced Matchings in Grids ⋮ Unnamed Item ⋮ Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ Maximum \(k\)-regular induced subgraphs ⋮ Minimum number of maximal dissociation sets in trees ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ An inequality for polymatroid functions and its applications. ⋮ Locally searching for large induced matchings ⋮ Donation center location problem ⋮ Degenerate matchings and edge colorings ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Induced matchings in asteroidal triple-free graphs ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem ⋮ Induced matchings in intersection graphs. ⋮ The cook-book approach to the differential equation method ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Two greedy consequences for maximum induced matchings ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ On minimum maximal distance-\(k\) matchings ⋮ On the complexity of bandwidth allocation in radio networks ⋮ Approximating weighted induced matchings ⋮ The efficiency of AC graphs ⋮ Connectivity, persistence and fault diagnosis of interconnection networks based on \(O_ k\) and \(2O_ k\) graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On the approximability of the maximum induced matching problem ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ Distance edge-colourings and matchings ⋮ On distance-3 matchings and induced matchings ⋮ Generalized subgraph-restricted matchings in graphs ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Number of induced matchings of graphs ⋮ Maximum induced matching of hexagonal graphs ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ New kernels for several problems on planar graphs ⋮ Some bounds on the maximum induced matching numbers of certain grids ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Equality of distance packing numbers ⋮ Efficient edge domination in regular graphs ⋮ Quadratic vertex kernel for rainbow matching ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ Induced Matchings in Graphs of Bounded Maximum Degree ⋮ The parameterized complexity of the induced matching problem ⋮ Maximum induced matching problem on hhd-free graphs ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ Improved Induced Matchings in Sparse Graphs ⋮ Recent progress on strong edge-coloring of graphs ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Brambles and independent packings in chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Certain NP-complete matching problems ⋮ Distributed link scheduling in wireless networks ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Independent packings in structured graphs ⋮ A generalization of extension complexity that captures P ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ Maximum induced matchings close to maximum matchings ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ On the complexity of a family of generalized matching problems ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ Vertex cover at distance on \(H\)-free graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs ⋮ Maximum induced matchings of random cubic graphs
Cites Work
This page was built for publication: NP-completeness of some generalizations of the maximum matching problem
