On the completeness of a generalized matching problem

DOI10.1145/800133.804353zbMath1282.68182OpenAlexW2045501273MaRDI QIDQ5402563

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800133.804353

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Related Items

Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths, Simplified group activity selection with group size constraints, On the complexity of the \(k\)-customer vehicle routing problem, An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs, Dealing with several parameterized problems by random methods, A parameterized perspective on packing paths of length two, Packings by Complete Bipartite Graphs, Computing phylogenetic roots with bounded degrees and errors is NP-complete, Graphs with maximal induced matchings of the same size, Induced star partition of graphs, Narrow sieves for parameterized paths and packings, Graph factors and factorization: 1985--2003: a survey, \(P_3\)-factors in the square of a tree, An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules, Local improvement algorithms for a path packing problem: a performance analysis based on linear programming, On the König graphs for a 5-path and its spanning supergraphs, A greedy algorithm for the social golfer and the Oberwolfach problem, Multi-shuttle crane scheduling in automated storage and retrieval systems, Matching and weighted \(P_2\)-packing: algorithms and kernels, Kernelization Algorithms for Packing Problems Allowing Overlaps, Maximum tree-packing in time \(O(n^{5/2})\), Maximum tree-packing in time O(n5/2), A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs, Star covers and star partitions of double-split graphs, Balanced tree partition problems with virtual nodes, On generalized matching problems, A local search algorithm for the \(k\)-path partition problem, Measuring the distance to series-parallelity by path expressions, On König graphs with respect to P4, Combinatorial and computational aspects of graph packing and graph decomposition, Maximum packing for biconnected outerplanar graphs, Packing paths: recycling saves time, Illuminating disjoint line segments in the plane, Improved Algorithms for Several Parameterized Problems Based on Random Methods, NP-completeness of graph decomposition problems, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, Path-factors in the square of a tree, Approximability results for the maximum and minimum maximal induced matching problems, Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, The path partition problem and related problems in bipartite graphs, Polynomial kernels for deletion to classes of acyclic digraphs, Bounded vertex colorings of graphs, Graph editing problems with extended regularity constraints, Approximation algorithms for some vehicle routing problems, Packing in honeycomb networks, A Problem Kernelization for Graph Packing, The complexity of dissociation set problems in graphs, An improved kernelization for \(P_{2}\)-packing, Partitioning graphs into induced subgraphs, Metabolic networks are NP-hard to reconstruct, König Graphs with Respect to the 4-Path and Its Spanning Supergraphs, Differential approximation of NP-hard problems with equal size feasible solutions, Packing paths perfectly, Treelike comparability graphs, Vertex and edge covers with clustering properties: Complexity and algorithms, Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps, Bandwidth contrained NP-complete problems, Approximation algorithms for min-sum \(p\)-clustering, Generalized partitions of graphs, Packing paths of length at least two, A Parameterized Perspective on Packing Paths of Length Two, On the complexity of partitioning graphs into connected subgraphs, Unnamed Item, On the structure of self-complementary graphs, Balanced partitions of trees and applications, Packings by cliques and by finite families of graphs, A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs, Covering tree with stars, On partial descriptions of König graphs for odd paths and all their spanning supergraphs