scientific article; zbMATH DE number 1305487

zbMath0938.68073MaRDI QIDQ4252376

Richard Beigel

Publication date: 17 June 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

maximum clique problemmaximum independent set problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (23)

Improved exact algorithms for MAX-SAT ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Strong computational lower bounds via parameterized complexity ⋮ Partition into triangles on bounded degree graphs ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Fast algorithms for max independent set ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ Stability preserving transformations of graphs ⋮ Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs ⋮ A note on the complexity of minimum dominating set ⋮ Open problems around exact algorithms ⋮ Exact algorithms for maximum independent set ⋮ Dynamic parameterized problems ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number ⋮ Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems ⋮ A 4D-sequencing approach for air traffic management ⋮ Solving NP-Complete Problems with Quantum Search ⋮ Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3 ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ Homogeneous genetic algorithms

This page was built for publication: