scientific article; zbMATH DE number 1263204

Sanjeev Arora, Marek Karpinski, David R. Karger

Publication date: 27 August 2001

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

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (50)

Complexity of finding dense subgraphs ⋮ Chromatic kernel and its applications ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ On the efficiency of polynomial time approximation schemes ⋮ Approximate and dynamic rank aggregation ⋮ Bounds on the max and min bisection of random cubic and random 4-regular graphs ⋮ A lower bound of $8/(7+\frac{1}{k-1})$ on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut ⋮ Random sampling and approximation of MAX-CSPs ⋮ Greedily finding a dense subgraph ⋮ Near optimal solutions for maximum quasi-bicliques ⋮ Integer and fractional packings in dense 3‐uniform hypergraphs ⋮ Unnamed Item ⋮ Constructing the highest degree subgraph for dense graphs is in ${\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}$ ⋮ An efficient algorithm for solving pseudo clique enumeration problem ⋮ Hardness of fully dense problems ⋮ Integer and fractional packings of hypergraphs ⋮ A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs ⋮ Finding connected $k$-subgraphs with high density ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms ⋮ The densest $k$-subgraph problem on clique graphs ⋮ Testability of minimum balanced multiway cut densities ⋮ Improved non-approximability results for vertex cover with density constraints ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Amplification and Derandomization without Slowdown ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ Unnamed Item ⋮ An Efficient Algorithm for Enumerating Pseudo Cliques ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ String-Matching and Alignment Algorithms for Finding Motifs in NGS Data ⋮ How to Cut a Graph into Many Pieces ⋮ Improved approximation algorithms for MAX $k$-cut and MAX BISECTION ⋮ Maximum dispersion problem in dense graphs ⋮ A constant approximation algorithm for the densest $k$-subgraph problem on chordal graphs ⋮ A new Lagrangian net algorithm for solving max-bisection problems ⋮ A multiple penalty function method for solving max-bisection problems ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ On point covers of $c-$oriented polygons ⋮ Polynomial time approximation schemes for dense instances of minimum constraint satisfaction ⋮ Partitioning problems in dense hypergraphs ⋮ A simple algorithm for the multiway cut problem ⋮ Unnamed Item ⋮ Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems ⋮ Balanced cut approximation in random geometric graphs ⋮ An improved approximation algorithm of MULTIWAY CUT. ⋮ Fast stabbing of boxes in high dimensions ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ A randomized approximation scheme for metric MAX-CUT

This page was built for publication: