On the completeness of a generalized matching problem
From MaRDI portal
Recommendations
Cited in
(94)- The labeled maximum matching problem
- Treelike comparability graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- On the complexity of partitioning graphs into connected subgraphs
- On the complexity of a family of generalized matching problems
- Packings by cliques and by finite families of graphs
- On generalized matching problems
- NP-completeness of graph decomposition problems
- Approximation algorithms for min-sum \(p\)-clustering
- Generalized partitions of graphs
- Maximum tree-packing in time \(O(n^{5/2})\)
- Illuminating disjoint line segments in the plane
- Optimal general matchings
- Polynomial kernels for deletion to classes of acyclic digraphs
- Approximation algorithms for some vehicle routing problems
- Metabolic networks are NP-hard to reconstruct
- Bandwidth contrained NP-complete problems
- Packing paths of length at least two
- On the complexity of the \(k\)-customer vehicle routing problem
- Maximum packing for biconnected outerplanar graphs
- Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
- On partial descriptions of König graphs for odd paths and all their spanning supergraphs
- Simplified group activity selection with group size constraints
- Induced star partition of graphs
- An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules
- A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
- The complexity of dissociation set problems in graphs
- On a conjecture by Gale about one-sided matching problems
- Balanced partitions of trees and applications
- A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
- Covering tree with stars
- Narrow sieves for parameterized paths and packings
- Graph matching problems and the NP-hardness of sortedness constraints
- Balanced tree partition problems with virtual nodes
- Packing paths: recycling saves time
- The path partition problem and related problems in bipartite graphs
- Dealing with several parameterized problems by random methods
- Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
- \(P_3\)-factors in the square of a tree
- Local improvement algorithms for a path packing problem: a performance analysis based on linear programming
- A greedy algorithm for the social golfer and the Oberwolfach problem
- Multi-shuttle crane scheduling in automated storage and retrieval systems
- Computational complexity of existence problems for matchings in graphs.
- Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
- Kernelization algorithms for packing problems allowing overlaps
- An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
- On the structure of self-complementary graphs
- Graphs with maximal induced matchings of the same size
- A Problem Kernelization for Graph Packing
- Packings by Complete Bipartite Graphs
- Matching and weighted \(P_2\)-packing: algorithms and kernels
- On the NP-completeness of the perfect matching free subgraph problem
- scientific article; zbMATH DE number 1341910 (Why is no real title available?)
- Differential approximation of NP-hard problems with equal size feasible solutions
- Combinatorial and computational aspects of graph packing and graph decomposition
- Improved algorithms for several parameterized problems based on random methods
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- König graphs with respect to the 4-path and its spanning supergraphs
- On the König graphs for a 5-path and its spanning supergraphs
- Graph editing problems with extended regularity constraints
- scientific article; zbMATH DE number 5691235 (Why is no real title available?)
- On König graphs with respect to P₄
- A Parameterized Perspective on Packing Paths of Length Two
- Kernelization of packing problems
- Maximum tree-packing in time O(n5/2)
- Star covers and star partitions of double-split graphs
- A local search algorithm for the k-path partition problem
- Measuring the distance to series-parallelity by path expressions
- Packing K_rs in bounded degree graphs
- An algorithmic framework for locally constrained homomorphisms
- Approximation algorithms for the maximum-weight cycle/path packing problems
- On star partition of split graphs
- Star covers and star partitions of cographs and butterfly-free graphs
- Improved approximation algorithms for cycle and path packings
- A deterministic approximation algorithm for metric triangle packing
- Improved approximation algorithms for the \(k\)-path partition problem
- An improved approximation algorithm for metric triangle packing
- Trimming forests is hard (unless they are made of stars)
- Degree conditions for path-factors in graphs
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Enumeration and asymptotic analysis of edge-disjoint triangle packings in complete graphs
- Bounded vertex colorings of graphs
- Improved approximations for the capacitated vehicle routing problem with fixed capacity
- Binding number conditions for path-factor uniform graphs
- Approximation algorithms for cycle and path partitions in complete graphs
- Packing in honeycomb networks
- Improved approximation algorithms for capacitated vehicle routing with fixed capacity
- Packing paths perfectly
- A parameterized perspective on packing paths of length two
- Computing phylogenetic roots with bounded degrees and errors is NP-complete
- Graph factors and factorization: 1985--2003: a survey
- Path-factors in the square of a tree
- Approximability results for the maximum and minimum maximal induced matching problems
- An improved kernelization for \(P_{2}\)-packing
This page was built for publication: On the completeness of a generalized matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402563)
