On the public citation graph

Spectral techniques in graph algorithms

https://doi.org/10.1007/bfb0054322
0 signed · 96 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-zopenalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-wopenalex-snapshot
Finding a large hidden clique in a random graph
inferredcites →https://doi.org/10.1002/rsa.3240030402openalex-snapshot
Large Cliques Elude the Metropolis Process
inferredcites →https://doi.org/10.1006/jagm.1995.1034openalex-snapshot
Coloring Random and Semi-Random k-Colorable Graphs
inferredcites →https://doi.org/10.1007/3-540-08442-8_114openalex-snapshot
Expected Behavior of Graph Coloring Algorithms
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2openalex-snapshot
Complexity of Computer Computations
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/978-3-540-68279-0_8openalex-snapshot
Reducibility Among Combinatorial Problems
inferredcites →https://doi.org/10.1007/bf01581168openalex-snapshot
Approximating the independence number via theϑ-function
inferredcites →https://doi.org/10.1007/bf01994876openalex-snapshot
Approximating maximum independent sets by excluding subgraphs
inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1007/bf02579166openalex-snapshot
Eigenvalues and expanders
inferredcites →https://doi.org/10.1007/bf02579196openalex-snapshot
The monotone circuit complexity of boolean functions
inferredcites →https://doi.org/10.1007/bf02579329openalex-snapshot
The eigenvalues of random symmetric matrices
inferredcites →https://doi.org/10.1016/0012-365x(89)90214-8openalex-snapshot
A randomised 3-colouring algorithm
inferredcites →https://doi.org/10.1016/0020-0190(92)90140-qopenalex-snapshot
Finding good approximate vertex and edge partitions is NP-hard
inferredcites →https://doi.org/10.1016/0166-218x(94)00103-kopenalex-snapshot
Expected complexity of graph partitioning problems
inferredcites →https://doi.org/10.1016/0196-6774(88)90005-3openalex-snapshot
Almost all k-colorable graphs are easy to color
inferredcites →https://doi.org/10.1016/0196-6774(89)90001-1openalex-snapshot
The solution of some random NP-hard problems in polynomial expected time
inferredcites →https://doi.org/10.1016/0890-5401(89)90067-9openalex-snapshot
Approximate counting, uniform generation and rapidly mixing Markov chains
inferredcites →https://doi.org/10.1016/0956-0521(91)90014-vopenalex-snapshot
Partitioning of unstructured problems for parallel processing
inferredcites →https://doi.org/10.1016/c2009-0-09109-0openalex-snapshot
Combinatorial Problems and Exercises
inferredcites →https://doi.org/10.1016/s0020-0190(96)00190-1openalex-snapshot
An algorithm for 3-colorable graphs
inferredcites →https://doi.org/10.1080/00401706.1966.10490393openalex-snapshot
A First Course in Numerical Analysis
inferredcites →https://doi.org/10.1090/chel/361openalex-snapshot
Combinatorial Problems and Exercises
inferredcites →https://doi.org/10.1109/ccc.1996.507690openalex-snapshot
Zero knowledge and the chromatic number
inferredcites →https://doi.org/10.1109/fscs.1990.89576openalex-snapshot
Some tools for approximate 3-coloring
inferredcites →https://doi.org/10.1109/sfcs.1984.715931openalex-snapshot
Eigenvalues, Expanders And Superconcentrators
inferredcites →https://doi.org/10.1109/sfcs.1987.22openalex-snapshot
Eigenvalues and graph bisection: An average-case analysis
inferredcites →https://doi.org/10.1109/sfcs.1988.21958openalex-snapshot
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
inferredcites →https://doi.org/10.1109/sfcs.1991.185341openalex-snapshot
Approximating clique is almost NP-complete
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1992.267824openalex-snapshot
Probabilistic checking of proofs; a new characterization of NP
inferredcites →https://doi.org/10.1109/sfcs.1994.365710openalex-snapshot
Approximate graph coloring by semidefinite programming
inferredcites →https://doi.org/10.1109/sfcs.1996.548468openalex-snapshot
Spectral partitioning works: planar graphs and finite element meshes
inferredcites →https://doi.org/10.1109/sfcs.1996.548522openalex-snapshot
Clique is hard to approximate within n/sup 1-ε/
inferredcites →https://doi.org/10.1109/tit.1979.1055985openalex-snapshot
On the Shannon capacity of a graph
inferredcites →https://doi.org/10.1111/j.1749-6632.1970.tb45136.xopenalex-snapshot
ON EIGENVALUES AND COLORINGS OF GRAPHS, II
inferredcites →https://doi.org/10.1137/0136016openalex-snapshot
A Separator Theorem for Planar Graphs
inferredcites →https://doi.org/10.1137/0611030openalex-snapshot
Partitioning Sparse Matrices with Eigenvectors of Graphs
inferredcites →https://doi.org/10.1137/s0097539794270248openalex-snapshot
A Spectral Technique for Coloring Random 3-Colorable Graphs
inferredcites →https://doi.org/10.1145/167088.167172openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/195058.195187openalex-snapshot
A spectral technique for coloring random 3-colorable graphs (preliminary version)
inferredcites →https://doi.org/10.1145/258533.258675openalex-snapshot
Eigenvalues, flows and separators of graphs
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
inferredcites →https://doi.org/10.1145/274787.274791openalex-snapshot
Approximate graph coloring by semidefinite programming
inferredcites →https://doi.org/10.1145/73007.73063openalex-snapshot
On the second eigenvalue of random regular graphs
inferredcites →https://doi.org/10.1147/rd.175.0420openalex-snapshot
Lower Bounds for the Partitioning of Graphs
inferredcites →https://doi.org/10.1201/9781420057140openalex-snapshot
Graph Theory and Its Applications
inferredcites →https://doi.org/10.21136/cmj.1973.101168openalex-snapshot
Algebraic connectivity of graphs
inferredcites →https://doi.org/10.5555/251040.251043openalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.5555/314613.315014openalex-snapshot
Finding a large hidden clique in a random graph

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/cpe.3499openalex-snapshot
Performance analysis of distributed symmetric sparse matrix vector multiplication algorithm for multi‐core architectures
inferred← citeshttps://doi.org/10.1002/rsa.70011openalex-snapshot
The Spectral Edge of Constant Degree Erdős–Rényi Graphs
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_3openalex-snapshot
Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time
inferred← citeshttps://doi.org/10.1007/978-0-387-09680-3_9openalex-snapshot
Partitioning Random Graphs with General Degree Distributions
inferred← citeshttps://doi.org/10.1007/978-0-387-34735-6_22openalex-snapshot
Spectral Partitioning of Random Graphs with Given Expected Degrees
inferred← citeshttps://doi.org/10.1007/978-3-031-01749-0openalex-snapshot
Analyzing Analytics
inferred← citeshttps://doi.org/10.1007/978-3-642-02026-1_18openalex-snapshot
On Construction of Almost-Ramanujan Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-34266-0_9openalex-snapshot
Linear Loss Function for the Network Blocking Game: An Efficient Model for Measuring Network Robustness and Link Criticality
inferred← citeshttps://doi.org/10.1007/978-3-642-34704-7_22openalex-snapshot
Towards Attack Resilient Social Network Based Threshold Signing
inferred← citeshttps://doi.org/10.1007/s00039-004-0478-3openalex-snapshot
Graph Products, Fourier Analysis and Spectral Techniques
inferred← citeshttps://doi.org/10.1007/s00440-015-0659-zopenalex-snapshot
Community detection in sparse networks via Grothendieck’s inequality
inferred← citeshttps://doi.org/10.1007/s00440-021-01054-4openalex-snapshot
Fluctuations of extreme eigenvalues of sparse Erdős–Rényi graphs
inferred← citeshttps://doi.org/10.1007/s00493-007-2190-zopenalex-snapshot
Spectral norm of random matrices
inferred← citeshttps://doi.org/10.1016/j.dam.2012.06.008openalex-snapshot
Approximating independent set in perturbed graphs
inferred← citeshttps://doi.org/10.1016/j.laa.2016.03.026openalex-snapshot
Sharp spectral bounds of several graph parameters using eigenvector norms
inferred← citeshttps://doi.org/10.1017/s0963548302005424openalex-snapshot
The Largest Eigenvalue of Sparse Random Graphs
inferred← citeshttps://doi.org/10.1023/a:1013899527204openalex-snapshot
Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time
inferred← citeshttps://doi.org/10.1073/pnas.0903215107openalex-snapshot
Stability of graph communities across time scales
inferred← citeshttps://doi.org/10.1103/physreve.75.036105openalex-snapshot
Structural bottlenecks for communication in networks
inferred← citeshttps://doi.org/10.1109/allerton.2008.4797702openalex-snapshot
Girth of the Tanner graph and error correction capability of LDPC codes
inferred← citeshttps://doi.org/10.1109/focs.2007.66openalex-snapshot
Mechanism Design via Differential Privacy
inferred← citeshttps://doi.org/10.1109/isit.2008.4595023openalex-snapshot
On the guaranteed error correction capability of LDPC codes
inferred← citeshttps://doi.org/10.1109/ita.2009.5044922openalex-snapshot
Guaranteed error correction capability of codes on graphs
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892064openalex-snapshot
Pseudorandom generators in propositional proof complexity
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959893openalex-snapshot
Lower bounds for polynomial calculus: non-binomial case
inferred← citeshttps://doi.org/10.1109/tcomm.2020.2987898openalex-snapshot
Analysis of the Error Correction Capability of LDPC and MDPC Codes Under Parallel Bit-Flipping Decoding and Application to Cryptography
inferred← citeshttps://doi.org/10.1109/tifs.2010.2093521openalex-snapshot
Exploiting Trust-Based Social Networks for Distributed Protection of Sensitive Data
inferred← citeshttps://doi.org/10.1109/tit.2010.2040962openalex-snapshot
On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes
inferred← citeshttps://doi.org/10.1109/wmvc.2008.4544062openalex-snapshot
Detecting Semantic Group Activities Using Relational Clustering
inferred← citeshttps://doi.org/10.1137/070699354openalex-snapshot
Finding Planted Partitions in Random Graphs with General Degree Distributions
inferred← citeshttps://doi.org/10.1145/1060590.1060654openalex-snapshot
Spectral norm of random matrices
inferred← citeshttps://doi.org/10.1145/1132952.1132954openalex-snapshot
Graph mining
inferred← citeshttps://doi.org/10.1145/1143997.1144193openalex-snapshot
Spectral techniques for graph bisection in genetic algorithms
inferred← citeshttps://doi.org/10.1145/1368310.1368358openalex-snapshot
Exploiting social networks for threshold signing
inferred← citeshttps://doi.org/10.1214/19-aihp1033openalex-snapshot
Spectral radii of sparse random matrices
inferred← citeshttps://doi.org/10.1214/20-aop1483openalex-snapshot
Extremal eigenvalues of critical Erdős–Rényi graphs
inferred← citeshttps://doi.org/10.1214/22-aop1596openalex-snapshot
Poisson statistics and localization at the spectral edge of sparse Erdős–Rényi graphs
inferred← citeshttps://doi.org/10.1587/transfun.e94.a.1247openalex-snapshot
Spectral Analysis of Random Sparse Matrices
inferred← citeshttps://doi.org/10.2200/s00449ed1v01y201209dmk006openalex-snapshot
Graph Mining: Laws, Tools, and Case Studies
inferred← citeshttps://doi.org/10.4230/lipics.isaac.2021.74openalex-snapshot
Large Minors in Expanders
inferred← citeshttps://doi.org/10.48550/arxiv.1412.3855openalex-snapshot
Necessary Spectral Conditions for Coloring Hypergraphs
inferred← citeshttps://doi.org/10.48550/arxiv.1704.02945openalex-snapshot
Spectral radii of sparse random matrices
inferred← citeshttps://doi.org/10.70675/b105e512z9823z437bz8552z15a1c0ddc12fopenalex-snapshot
Grandes valeurs propres de graphes aléatoires dilués
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.