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