Measure and conquer

DOI10.1145/1109557.1109560MaRDI QIDQ3581486zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch

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

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

Cited in

(35)

• A heuristic approach for the max-min diversity problem based on max-clique
• On comparing algorithms for the maximum clique problem
• New potential functions for greedy independence and coloring
• Iterative compression and exact algorithms
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Computing optimal Steiner trees in polynomial space
• Computing the differential of a graph: hardness, approximability and exact algorithms
• 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
• An Improved SAT Algorithm in Terms of Formula Length
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Faster Steiner Tree Computation in Polynomial-Space
• Iterative Compression and Exact Algorithms
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Confronting intractability via parameters
• Independent sets in graphs
• Algorithmic data science (invited talk)
• On Independent Sets and Bicliques in Graphs
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• 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
• Learning-augmented maximum independent set
• On maximum independent sets in \(P_{5}\)-free graphs
• Isolation concepts for efficiently enumerating dense subgraphs
• Improved edge-coloring with three colors
• 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
• Computing branchwidth via efficient triangulations and blocks
• Efficient algorithms for clique problems
• Approximation of min coloring by moderately exponential algorithms
• Exponential-time approximation of weighted set cover

This page was built for publication: Measure and conquer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581486)