On the approximability of the maximum common subgraph problem

DOI10.1007/3-540-55210-3_198zbMath1494.68196OpenAlexW1605991832MaRDI QIDQ5096796

Viggo Kann

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_198

zbMATH Keywords

computational complexityapproximationgraph problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (23)

Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees ⋮ Capacity inverse minimum cost flow problems under the weighted Hamming distance ⋮ 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 ⋮ On the complexity of compressing two dimensional routing tables with order ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Beyond rankings: comparing directed acyclic graphs ⋮ 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 ⋮ A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree ⋮ Approximate solution of NP optimization problems ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ A fast discovery algorithm for large common connected induced subgraphs ⋮ Unnamed Item ⋮ Exact localisations of feedback sets ⋮ On parameterized complexity of the multi-MCS problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Matching theory
• The complexity of optimization problems
• The Steiner problem with edge lengths 1 and 2
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for combinatorial problems
• Subgraph isomorphism, matching relational structures and maximal cliques
• Logical definability of NP optimization problems
• Worst-case analysis of a new heuristic for the travelling salesman problem
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Edge-Deletion Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Linear approximation of shortest superstrings
• On the complexity of approximating the independent set problem

This page was built for publication: On the approximability of the maximum common subgraph problem