On the approximability of the maximum common subgraph problem
From MaRDI portal
Recommendations
Cites work
- Approximating maximum independent sets by excluding subgraphs
- Approximation algorithms for combinatorial problems
- Edge-Deletion Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- scientific article; zbMATH DE number 4155842 (Why is no real title available?)
- scientific article; zbMATH DE number 17535 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Linear approximation of shortest superstrings
- Logical definability of NP optimization problems
- Matching theory
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- On the complexity of approximating the independent set problem (extended abstract)
- Subgraph isomorphism, matching relational structures and maximal cliques
- The complexity of optimization problems
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- The Steiner problem with edge lengths 1 and 2
- Worst-case analysis of a new heuristic for the travelling salesman problem
Cited in
(38)- On parameterized complexity of the multi-MCS problem
- On the approximation of largest common subtrees and largest common point sets
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- On the complexity of compressing two dimensional routing tables with order
- Beyond rankings: comparing directed acyclic graphs
- A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
- The maximum common edge subgraph problem: A polyhedral investigation
- Polyhedral study of the maximum common induced subgraph problem
- An approximation algorithm for the maximum spectral subgraph problem
- A fast discovery algorithm for large common connected induced subgraphs
- Tight FPT approximation for constrained k-center and k-supplier
- A branch \& cut algorithm for the maximum common edge subgraph problem
- Approximate graph isomorphism
- Capacity inverse minimum cost flow problems under the weighted Hamming distance
- Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms
- scientific article; zbMATH DE number 1555958 (Why is no real title available?)
- The approximation of maximum subgraph problems
- Polynomially bounded minimization problems which are hard to approximate
- Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
- The feedback arc set problem with triangle inequality is a vertex cover problem
- The Complexity of Mining Maximal Frequent Subgraphs
- Algorithmic data science (invited talk)
- Approximation hardness of the cross-species conserved active modules detection problem
- Multicommodity flow in trees: packing via covering and iterated relaxation
- Aligning and Labeling Genomes under the Duplication-Loss Model
- Structure in approximation classes
- On the approximability of path and cycle problems in arc-dependent networks
- Reachability in choice networks
- Geometric dominating-set and set-cover via local-search
- On the complexity of minimum maximal acyclic matchings
- Optimal length cutting plane refutations of integer programs
- Euclidean TSP in narrow strips
- Approximate solution of NP optimization problems
- Optimal length cutting plane refutations of integer programs
- Geometric TSP on sets
- Exact localisations of feedback sets
- Largest common subgraph of two forests
- Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
This page was built for publication: On the approximability of the maximum common subgraph problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096796)
