Expected complexity of graph partitioning problems

DOI10.1016/0166-218X(94)00103-KMaRDI QIDQ1346695zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Luděk Kučera

Publication date 10 April 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)00103-k

zbMATH Keywords

time complexitygraph partitioning problems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Recommendations

• The solution of some random NP-hard problems in polynomial expected time
• A linear time algorithm for graph partition problems
• Linear-Time Approximation Algorithms for the Max Cut Problem
• scientific article; zbMATH DE number 1962838
• Deciding \(k\)-colorability in expected polynomial time

Cites work

• scientific article; zbMATH DE number 4213473 (Why is no real title available?)
• scientific article; zbMATH DE number 3608053 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Almost all k-colorable graphs are easy to color
• Graphs with small chromatic numbers are easy to color
• On colouring random graphs
• The chromatic number of random graphs
• The greedy coloring is a bad probabilistic algorithm
• The solution of some random NP-hard problems in polynomial expected time

Cited in

(29)

• Finding hidden cliques in linear time with high probability
• Comment on ``Hypothesis testing by convex optimization
• Recovering nonuniform planted partitions via iterated projection
• On the hardness of designing public signals
• The Ehrenfeucht-Fraïssé method and the planted clique conjecture
• Computational barriers in minimax submatrix detection
• The solution of some random NP-hard problems in polynomial expected time
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Hardness self-amplification: simplified, optimized, and unified
• Algorithms approaching the threshold for semi-random planted clique
• Cryptography from planted graphs: security with logarithmic-size messages
• How to hide a clique?
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Optimal detection of sparse principal components in high dimension
• The forgetfulness of balls and bins
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Finding a planted clique by adaptive probing
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• Simple probabilistic analysis to generalize bottleneck graph multi-partitioning
• A nearly tight sum-of-squares lower bound for the planted clique problem
• A simple spectral algorithm for recovering planted partitions
• A note on edge-based graph partitioning and its linear algebraic structure
• The complexity of explicit constructions
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• The Complexity of Public-Key Cryptography
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• scientific article; zbMATH DE number 4043263 (Why is no real title available?)

This page was built for publication: Expected complexity of graph partitioning problems

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