NDLI: Approximation and intractability results for the maximum cut problem and its variants

Content Provider	IEEE Xplore Digital Library
Author	Haglin, D.J. Venkatesan, S.M.
Copyright Year	1968
Abstract	The maximum cut problem is known to be an important NP-complete problem with many applications. The authors investigate this problem (which they call the normal maximum cut problem) and a variant of it (which is referred to as the connected maximum cut problem). They show that any n-vertex e-edge graph admits a cut with at least the fraction 1/2+1/2n of its edges, thus improving the ratio 1/2+2/e known before. It is shown that it is NP-complete to decide if a given graph has a normal maximum cut with at least a fraction (1/2+ epsilon ) of its edges, where the positive constant epsilon can be taken smaller than any value chosen. The authors present an approximation algorithm for the normal maximum cut problem on any graph that runs in O((e log e+n log n)/p+log p*log n) parallel time using p(1>
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	110
Ending Page	113
Page Count	4
File Size	487234
File Format	PDF
ISSN	00189340
Volume Number	40
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1991-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation algorithms Polynomials Concurrent computing H infinity control Computer science Computational modeling History
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A residue arithmetic extension for reliable scientific computation

NC algorithms for recognizing chordal graphs and k trees

On hardware for computing exponential and trigonometric functions

Optimal centralized algorithms for store-and-forward deadlock avoidance

Mesh computer algorithms for computational geometry

Design of a radix 4 division unit with simple selection table

A parallel time/hardware tradeoff T.H=O(2/sup n/2/) for the knapsack problem

A clustered failure model for the memory array reconfiguration problem

Task allocation on a network of processors

Approximation and intractability results for the maximum cut problem and its variants

Similar Documents

A residue arithmetic extension for reliable scientific computation

NC algorithms for recognizing chordal graphs and k trees

On hardware for computing exponential and trigonometric functions

Optimal centralized algorithms for store-and-forward deadlock avoidance

Mesh computer algorithms for computational geometry

Design of a radix 4 division unit with simple selection table

A parallel time/hardware tradeoff T.H=O(2/sup n/2/) for the knapsack problem

A clustered failure model for the memory array reconfiguration problem

Task allocation on a network of processors

Approximation and intractability results for the maximum cut problem and its variants