On the Shannon capacity of a graph
From MaRDI portal
Publication:4178914
DOI10.1109/TIT.1979.1055985zbMATH Open0395.94021DBLPjournals/tit/Lovasz79WikidataQ29013070 ScholiaQ29013070MaRDI QIDQ4178914FDOQ4178914
Authors: László Lovász 
Publication date: 1979
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Recommendations
Petersen graphpentagonself-complementary graphShannon zero error capacityvertex transitive automorphism group
Cited In (only showing first 100 items - show all)
- Vector representation of graph domination
- Asymptotic values of the Hall-ratio for graph powers
- On the rank of a matrix associated with a graph.
- Positive matching decompositions of graphs
- On cover-structure graphs
- Classes of representable disjoint \textsf{NP}-pairs
- Applications of Ramsey theory
- A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
- Heuristics for semirandom graph problems
- An exponential gap with the removal of one negation gate
- The minimum rank problem for circulants
- A survey on graphs with convex quadratic stability number
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- A note on vector representation of graphs
- Geometric representations of graphs
- Role of redundant constraints for improving dual bounds in polynomial optimization problems
- Some observations on the smallest adjacency eigenvalue of a graph
- On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
- Zero-error stationary coding over stationary channels
- Laplacian eigenvalues and fixed size multisection
- Relative capacity and dimension of graphs
- On NP-hardness of the clique partition -- independence number gap recognition and related problems
- On the bandwidth of the Kneser graph
- Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited
- Triangle free graphs that are not \(\sqrt{3}\)-embeddable in \(S^ n\).
- On circular-perfect graphs: a survey
- Stability for intersecting families in \(\mathrm{PGL}(2,q)\)
- Algorithmic and explicit determination of the Lovász number for certain circulant graphs
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- Primal-dual first-order methods for a class of cone programming
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks
- On the conjunctive capacity of graphs
- On the density of sequences of integers the sum of no two of which is a square. I: Arithmetic progressions
- On coverings of tori with cubes
- Developments in the theory of graph spectra
- On the capacity of uniform hypergraphs
- The complexity of unions of disjoint sets
- Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem
- A sequential elimination algorithm for computing bounds on the clique number of a graph
- Bicliques and eigenvalues
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- On the dimension to represent a graph by a unit distance graph
- Probabilistic refinement of the asymptotic spectrum of graphs
- On the bounds for the ultimate independence ratio of a graph
- On the Shannon capacity of a directed graph
- A new linear programming algorithm - better or worse than the simplex method?
- The minrank of random graphs over arbitrary fields
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Constructive lower bounds for off-diagonal Ramsey numbers
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Improving an upper bound on the size of \(k\)-regular induced subgraphs
- Linearly independent vertices and minimum semidefinite rank
- Relaxations of combinatorial problems via association schemes
- Lower bounds in minimum rank problems
- On minrank and forbidden subgraphs
- An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
- Computing the Grothendieck constant of some graph classes
- Independence numbers of product graphs
- Sylow subgraphs in self-complementary vertex transitive graphs
- The Laplacian spectral radius of a graph under perturbation
- Sperner capacities
- Privileged users in zero-error transmission over a noisy channel
- Graphs associated with vector spaces of even dimension: A link with differential geometry
- The Erdős matching conjecture and concentration inequalities
- A semidefinite programming-based heuristic for graph coloring
- A new approach to the stable set problem based on ellipsoids
- Shannon zero error capacity in the problems of state estimation and stabilization via noisy communication channels
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- On standard quadratic programs with exact and inexact doubly nonnegative relaxations
- New lower bounds for the Shannon capacity of odd cycles
- Spectral operators of matrices
- Optimality theorems for convex semidefinite vector optimization problems
- Eigenvalue interlacing and weight parameters of graphs
- Approximating projections by quantum operations
- Tensor theta norms and low rank recovery
- Orthogonal representations and connectivity of graphs
- Quadratic factorization heuristics for copositive programming
- Exploring the relationship between max-cut and stable set relaxations
- Semidefinite programming in combinatorial optimization
- Grothendieck-type inequalities in combinatorial optimization
- Geometrical embeddings of graphs
- Eternal and Secure Domination in Graphs
- Independent sets in graphs
- An upper bound on the independence number of a graph computable in polynomial-time
- Relaxations of vertex packing
- A new branch-and-bound algorithm for standard quadratic programming problems
- A cross-intersection theorem for vector spaces based on semidefinite programming
- Regular inference as vertex coloring
- The gap between monotone and non-monotone circuit complexity is exponential
- Spectral bounds for the independence ratio and the chromatic number of an operator
- A limit theorem for the Shannon capacities of odd cycles I
- Orthogonal representations over finite fields and the chromatic number of graphs
- On hypercube packings, blocking sets and a covering problem
- Strong lift-and-project cutting planes for the stable set problem
- Grothendieck inequalities for semidefinite programs with rank constraint
- Beyond the Erdős-Ko-Rado theorem
- Combining semidefinite and polyhedral relaxations for integer programs
- Cutting planes in integer and mixed integer programming
- Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
This page was built for publication: On the Shannon capacity of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4178914)
