scientific article
From MaRDI portal
Publication:3128896
zbMath0873.68163MaRDI QIDQ3128896
Publication date: 29 October 1997
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (23)
It is hard to know when greedy is good for finding independent sets ⋮ Ultimate greedy approximation of independent sets in subcubic graphs ⋮ On sorting unsigned permutations by double-cut-and-joins ⋮ On approximation properties of the Independent set problem for degree 3 graphs ⋮ Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles) ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ The limits of local search for weighted \(k\)-set packing ⋮ Improved approximations for maximum independent set via approximation chains ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations ⋮ Constant-degree graph expansions that preserve treewidth ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ Approximating k-set cover and complementary graph coloring ⋮ An approximation of the minimum vertex cover in a graph ⋮ Unnamed Item ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles) ⋮ Stackelberg strategies on epidemic containment games ⋮ Improved approximations of independent dominating set in bounded degree graphs ⋮ The limits of local search for weighted \(k\)-set packing ⋮ Independent sets in bounded-degree hypergraphs ⋮ Some APX-completeness results for cubic graphs ⋮ Derandomized graph products
This page was built for publication:
