Measure and conquer

DOI10.1145/1109557.1109560zbMath1192.68960OpenAlexW4251769540WikidataQ60488762 ScholiaQ60488762MaRDI QIDQ3581486

Fedor V. Fomin, Dieter Kratsch, Fabrizio Grandoni

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109560

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01)

Related Items (34)

Isolation concepts for efficiently enumerating dense subgraphs ⋮ Improved edge-coloring with three colors ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ On Independent Sets and Bicliques in Graphs ⋮ An Improved SAT Algorithm in Terms of Formula Length ⋮ Computing optimal Steiner trees in polynomial space ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ On comparing algorithms for the maximum clique problem ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ Stability preserving transformations of graphs ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ Confronting intractability via parameters ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Independent sets in graphs ⋮ Solving connected dominating set faster than \(2^n\) ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Finding a dominating set on bipartite graphs ⋮ New potential functions for greedy independence and coloring ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Efficient algorithms for clique problems ⋮ On maximum independent sets in \(P_{5}\)-free graphs ⋮ Iterative compression and exact algorithms ⋮ Iterative Compression and Exact Algorithms ⋮ Unnamed Item ⋮ Approximation of min coloring by moderately exponential algorithms ⋮ Exponential-time approximation of weighted set cover ⋮ A 4D-sequencing approach for air traffic management ⋮ On the independent set problem in random graphs ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ A heuristic approach for the max-min diversity problem based on max-clique

This page was built for publication: Measure and conquer