Treffer: Algorithmic and explicit determination of the Lovász number for certain circulant graphs
Title:
Algorithmic and explicit determination of the Lovász number for certain circulant graphs
Authors:
Source:
3rd Cologne/Twente Workshop on Graphs and Combinatorial OptimizationDiscrete applied mathematics. 155(14):1812-1825
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 29 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Algèbre, Algebra, Géométrie algébrique, Algebraic geometry, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithmique, Algorithmics, Algorítmica, Calcul automatique, Computing, Cálculo automático, Combinatoire, Combinatorics, Combinatoria, Degré graphe, Graph degree, Grado grafo, Graphe circulant, Circulant graph, Grafo circulante, Informatique théorique, Computer theory, Informática teórica, Optimisation, Optimization, Optimización, Programmation linéaire, Linear programming, Programación lineal, 14H42, 68Wxx, Algorithme graphe, Graph algorithm, Lovász theta-function, Shannon capacity
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Mathematics Department, SUNY Buffalo State College, Buffalo, NY 14222, United States
ISSN:
0166-218X
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Mathematics
Mathematics
Accession Number:
edscal.19046562
Database:
PASCAL Archive
Weitere Informationen
We consider the problem of computing the Lovász theta function for circulant graphs Cn,J of degree four with n vertices and chord length J, 2 < J ≤ n. We present an algorithm that takes O(J) operations if J is an odd number, and O(n/J) operations if J is even. On the considered class of graphs our algorithm strongly outperforms the known algorithms for theta function computation. We also provide explicit formulas for the important special cases J = 2 and J = 3.