NP-completeness of some generalizations of the maximum matching problem

DOI10.1016/0020-0190(82)90077-1MaRDI QIDQ1168728zbMATH OpenOpenAlexWikidataFDO

Authors 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

zbMATH Keywords

communication network testingcomputational complexityNP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• On the np-completeness of certain network testing problems
• Some simplified NP-complete graph problems
• The complexity of satisfiability problems
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(only showing first 100 items - show all)

• Efficient edge domination in regular graphs
• Maximum induced matchings for chordal graphs in linear time
• The parameterized complexity of the induced matching problem
• Brambles and independent packings in chordal graphs
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• On the complexity of a family of generalized matching problems
• Connectivity, persistence and fault diagnosis of interconnection networks based on \(O_ k\) and \(2O_ k\) graphs
• An inequality for polymatroid functions and its applications.
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Maximum induced matchings of random cubic graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Locally searching for large induced matchings
• Degenerate matchings and edge colorings
• Parameterized algorithms and kernels for rainbow matching
• Approximating weighted induced matchings
• On the approximability of the maximum induced matching problem
• Generalized subgraph-restricted matchings in graphs
• Finding a maximum induced matching in weakly chordal graphs
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Donation center location problem
• Maximum induced matching algorithms via vertex ordering characterizations
• Approximating maximum acyclic matchings by greedy and local search strategies
• Maximum weight induced matching in some subclasses of bipartite graphs
• Number of induced matchings of graphs
• Vertex cover at distance on \(H\)-free graphs
• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
• On the computational complexity of the Helly number in the \(P_3\) and related convexities
• Acyclic matchings in graphs of bounded maximum degree
• A characterization of well-indumatchable graphs having girth greater than seven
• Parameterized algorithms and kernels for almost induced matching
• On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
• The complexity of dissociation set problems in 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
• On some hard and some tractable cases of the maximum acyclic matching problem
• Quadratic vertex kernel for rainbow matching
• Approximating maximum uniquely restricted matchings in bipartite graphs
• A generalization of extension complexity that captures P
• Maximum induced matchings close to maximum matchings
• Moderately exponential time algorithms for the maximum induced matching problem
• Exact algorithms for maximum induced matching
• On the hardness of deciding the equality of the induced and the uniquely restricted matching number
• Maximum \(k\)-regular induced subgraphs
• Generalizing the induced matching by edge capacity constraints
• Equality of distance packing numbers
• The graphs with maximum induced matching and maximum matching the same size
• Independent packings in structured graphs
• Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model
• Perfectly matched sets in graphs: parameterized and exact computation
• Induced matchings in graphs of bounded maximum degree
• Induced Matching in Some Subclasses of Bipartite Graphs
• 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
• Squares of Intersection Graphs and Induced Matchings
• Graphs with maximal induced matchings of the same size
• On distance-3 matchings and induced matchings
• Improved induced matchings in sparse graphs
• Induced matchings in subcubic graphs without short cycles
• Editing graphs to satisfy degree constraints: a parameterized approach
• Maximum Induced Matchings in Grids
• The cook-book approach to the differential equation method
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
• Two greedy consequences for maximum induced matchings
• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Well-indumatched Trees and Graphs of Bounded Girth
• On minimum maximal distance-\(k\) matchings
• Parameterized Algorithms and Kernels for Rainbow Matching
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• Maximum induced matching algorithms via vertex ordering characterizations
• Recent progress on strong edge-coloring of graphs
• Some bounds on the maximum induced matching numbers of certain grids
• Induced matchings in graphs of degree at most 4
• Distributed link scheduling in wireless networks
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
• Parameterized complexity of perfectly matched sets
• On the parameterized complexity of the acyclic matching problem
• Computational complexity aspects of super domination
• Improved induced matchings in sparse graphs
• Minimum number of maximal dissociation sets in trees
• Multi-channel assignment and link scheduling for prioritized latency-sensitive applications
• A bisection approach to subcubic maximum induced matching
• Cutting Barnette graphs perfectly is hard
• On the complexity of minimum maximal acyclic matchings
• Polyhedral approach to weighted connected matchings in general graphs
• An improved kernel and parameterized algorithm for almost induced matching
• Edge open packing: complexity, algorithmic aspects, and bounds
• Parameterized results on acyclic matchings with implications for related problems
• Well-indumatched pseudoforests
• Complexity of deciding the equality of matching numbers
• The efficiency of AC graphs
• The algorithmic complexity of the paired matching problem
• The minimum number of maximal dissociation sets in unicyclic graphs
• Social distancing as a population game in networked social environments
• Maximal and maximum induced matchings in connected graphs
• \(\mathcal{P}\)-matchings parameterized by treewidth

This page was built for publication: NP-completeness of some generalizations of the maximum matching problem

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