Maximum bounded 3-dimensional matching is MAX SNP-complete
From MaRDI portal
Recommendations
- Maximum bounded \(H\)-matching is Max SNP-complete
- Three-dimensional matching instances are rich in stable matchings
- Tight bounds on maximal and maximum matchings
- scientific article; zbMATH DE number 2081000
- Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph
- Three-Dimensional Stabl Matching Problems
- Bounds on maximum \(b\)-matchings
- Parameterizing MAX SNP Problems Above Guaranteed Values
- scientific article; zbMATH DE number 4114698
- Publication:4953913
Cites work
Cited in
(only showing first 100 items - show all)- Hardness of approximation for orthogonal rectangle packing and covering problems
- On the approximability of the maximum agreement subtree and maximum compatible tree problems
- An improved randomized approximation algorithm for maximum triangle packing
- Some MAX SNP-hard results concerning unordered labeled trees
- Maximum bounded \(H\)-matching is Max SNP-complete
- The hardness of approximation: Gap location
- Polynomial time approximation schemes for class-constrained packing problems
- Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs.
- Some APX-completeness results for cubic graphs
- Improved approximation algorithms for weighted 2-path partitions
- Distributed backup placement in networks
- Order consolidation for batch processing
- Conversion of coloring algorithms into maximum weight independent set algorithms
- Designing optimally multiplexed SNP genotyping assays
- Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive
- Flexible allocation on related machines with assignment restrictions
- A genetic-based framework for solving (multi-criteria) weighted matching problems.
- Packing triangles in bounded degree graphs.
- Approximation algorithms for NMR spectral peak assignment.
- Between a rock and a hard place: the two-to-one assignment problem
- A 6/5-approximation algorithm for the maximum 3-cover problem
- Generalized budgeted submodular set function maximization
- An improved approximation algorithm for the minimum common integer partition problem
- Distributed algorithms for matching in hypergraphs
- Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
- Computing envy-freeable allocations with limited subsidies
- Approximation algorithms for clustering with dynamic points
- The generalized definitions of the two-dimensional largest common substructure problems
- The power of one evil secret agent
- Independent sets in Line of Sight networks
- Strongly budget balanced auctions for multi-sided markets
- Multi-dimensional vector assignment problems
- The hypergraph assignment problem
- Finding disjoint paths in networks with star shared risk link groups
- Approximability and parameterized complexity of multicover by \(c\)-intervals
- Complexity of approximating bounded variants of optimization problems
- Hardness and approximation results for packing Steiner trees
- Matroid representation of clique complexes
- Least and most colored bases
- Partition into triangles on bounded degree graphs
- Tai mapping hierarchy for rooted labeled trees through common subforest
- Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
- Triangle strings: structures for augmentation of vertex-disjoint triangle sets
- Computing the differential of a graph: hardness, approximability and exact algorithms
- An approximation algorithm for maximum triangle packing
- A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
- The generalized assignment problem with minimum quantities
- Multi-shuttle crane scheduling in automated storage and retrieval systems
- An improved kernel for planar vertex-disjoint triangle packing
- Tractable and intractable variations of unordered tree edit distance
- There is no asymptotic PTAS for two-dimensional vector packing
- Improved MAX SNP-hard results for finding an edit distance between unordered trees
- Partition into triangles on bounded degree graphs
- Approximation and nonapproximability for the one-sided scaffold filling problem
- Improved approximation algorithms for weighted 2-path partitions
- Generalized hypergraph matching via iterated packing and local ratio
- A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
- APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
- Geometric Packing under Nonuniform Constraints
- Bin packing with fragmentable items: presentation and approximations
- Generalized budgeted submodular set function maximization
- Scalable algorithms for multiple network alignment
- On approximation properties of the Independent set problem for degree 3 graphs
- Approximability of average completion time scheduling on unrelated machines
- Packing sporadic real-time tasks on identical multiprocessor systems
- On the approximability of the maximum common subgraph problem
- scientific article; zbMATH DE number 7238962 (Why is no real title available?)
- Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
- Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
- Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
- Hardness and Approximation of Traffic Grooming
- COLORING ALGORITHMS ON SUBCUBIC GRAPHS
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- A randomized approximation algorithm for metric triangle packing
- Computational complexity characterization of protecting elections from bribery
- A fixed-parameter-tractable algorithm for set packing
- On the complexity of comparing evolutionary trees
- Hardness of \(k\)-vertex-connected subgraph augmentation problem
- Ascending-price mechanism for general multi-sided markets
- scientific article; zbMATH DE number 7764108 (Why is no real title available?)
- Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
- Cost-sharing games with rank-based utilities
- Shortest path and maximum flow problems in networks with additive losses and gains
- Approximating Bin Packing with Conflict Graphs via Maximization Techniques
- Packing K_rs in bounded degree graphs
- Minimizing total completion time with machine-dependent priority lists
- A deterministic approximation algorithm for metric triangle packing
- Matchings under distance constraints. II.
- An improved approximation algorithm for metric triangle packing
- Alignment of trees -- an alternative to tree edit
- Completion of partial Latin hypercube designs: NP-completeness and inapproximability
- Approximation algorithms for non-sequential star packing problems
- The price of fairness and stability in resource buying games
- On the generalized mean densest subgraph problem: complexity and algorithms
- Budgeted matroid maximization: a parameterized viewpoint
- Complexity of fixed order routing
- Approximation algorithms for the k^+-star packing problem
- Cost-sharing games with rank-based utilities
- Approximation algorithms for non-sequential star packing problems
- Inapproximability results for no-wait job shop scheduling.
This page was built for publication: Maximum bounded 3-dimensional matching is MAX SNP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922700)
