Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

Full text

Pdf (744 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 100 - 105

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Avrim Blum	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Goran Konjevod	Dept. of Math. Sciences, Carnegie Mellon University, Pittsburgh, PA
R. Ravi	GSlA, Carnegie Mellon University, Pittsburgh, PA
Santosh Vempala	Department of Mathematics, Massachusetts Institute of Technology, Cambridgem MA and School of Computer Science, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 17, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276717 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P, Chinn, J. Chvfitalovlt, A. Dewdney, N. Gibbs, The bandwidth problem for graphs and matrices--a survey, J. Graph Theory, 6: 223-254,1982.
	2	F. R. Chung , P. D. Seymour, Graphs with small bandwidth and cutwidth, Discrete Mathematics, v.75 n.1-3, p.113-119, 1989 [doi>10.1016/0012-365X(89)90083-6]
	3	V, Chv,~tal, A remark on a problem of Harary, Czechoslovak MathJ, 20: 109-111,1970.
	4	Uriel Feige, Approximating the bandwidth via volume respecting embeddings (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.90-99, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276716]
	5	M Garey, R. Graham, D. Johnson, D. E. Knuth, Complexity results for bandwidth minimization, SIAM J. Appl. Math. 34: 477-495,1978.
	6	M. Gr6tschel, L. Lov,Ssz, A. Sehrijver, Geometn'c Algorithms and Combinatorial Optimiza~on, Springer, 1988.
	7	J. Haralambides, E Make. don, B. Monien, Bandv,,idth minimization: an approximation algorithm for caterpillars, Math Systems Theory, 24:169-177,1991.
	8	Ton Kloks , Dieter Kratsch , Haiko Müller, Approximating the Bandwidth for Asteroidal Triple-Free Graphs, Proceedings of the Third Annual European Symposium on Algorithms, p.434-447, September 25-27, 1995
	9	Burkhard Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM Journal on Algebraic and Discrete Methods, v.7 n.4, p.505-512, Oct. 1986 [doi>10.1137/0607057]
	10	C.H. Papadimitriou, The NP-completeness of the bandwidth minimization problem, Computing, 16: 263-270, 1976.

CITED BY 6

	Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Anupam Gupta, Improved bandwidth approximation for trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.788-793, January 09-11, 2000, San Francisco, California, United States
	John Dunagan , Santosh Vempala, Optimal outlier removal in high-dimensional, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.627-636, July 2001, Hersonissos, Greece
	Uriel Feige, Approximating the bandwidth via volume respecting embeddings (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.90-99, May 24-26, 1998, Dallas, Texas, United States
	Pinar Heggernes , Dieter Kratsch , Daniel Meister, Bandwidth of bipartite permutation graphs in polynomial time, Journal of Discrete Algorithms, v.7 n.4, p.533-544, December, 2009