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

computational complexityNP-completenesscommunication network testing

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)

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

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)