Treffer: MAX CUT in cubic graphs
Title:
MAX CUT in cubic graphs
Authors:
Source:
Journal of algorithms (Print). 53(2):169-185
Publisher Information:
San Diego, CA: Elsevier, 2004.
Publication Year:
2004
Physical Description:
print, 12 ref
Original Material:
INIST-CNRS
Subject Terms:
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, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Programmation mathématique, Mathematical programming, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme approximation, Approximation algorithm, Algoritmo aproximación, Coupe graphe, Graph cut, Corte grafo, Degré graphe, Graph degree, Grado grafo, Graphe cubique, Cubic graph, Grafo cúbico, Graphe régulier, Regular graph, Grafo regular, Programmation semi définie, Semi definite programming, Programacíon semi definida, 68R10, Algorithme combinatoire, Combinatorial algorithm
Document Type:
Fachzeitschrift
Article
File Description:
text
Language:
English
Author Affiliations:
Computer Science Division, University of California at Berkeley, Berkeley, CA 94720-1776, United States
School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
ISSN:
0196-6774
Rights:
Copyright 2004 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
Operational research. Management
Mathematics
Operational research. Management
Accession Number:
edscal.16232417
Database:
PASCAL Archive
Weitere Informationen
We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least 0.9326. This improves, and also somewhat simplifies, a result of Feige, Karpinski and Langberg. We also observe that results of Hopkins and Staton and of Bondy and Locke yield a simple combinatorial 4/5-approximation algorithm for the problem. Finally, we present a combinatorial 22/27-approximation algorithm for the MAX CUT problem for regular cubic graphs.