{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:14:22Z","timestamp":1760440462107},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1991,12,1]],"date-time":"1991-12-01T00:00:00Z","timestamp":691545600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1991,12]]},"DOI":"10.1007\/bf02257778","type":"journal-article","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T19:01:28Z","timestamp":1132686088000},"page":"343-353","source":"Crossref","is-referenced-by-count":9,"title":["\u03b1-Vertex separator is NP-hard even for 3-regular graphs"],"prefix":"10.1007","volume":"46","author":[{"given":"R.","family":"M\u00fcller","sequence":"first","affiliation":[]},{"given":"D.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02257778_CR1","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T. N. Bui","year":"1987","unstructured":"[BCLS87] Bui, T. N., Chaudhuri, S., Leighton, F. T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica7, 171\u2013191 (1987).","journal-title":"Combinatorica"},{"key":"BF02257778_CR2","unstructured":"[Bo87] Bodl\u00e4nder, H. L.: Dynamic programming on graphs with bounded tree width. Report RUU-CS-87-22 University of Utrecht (1987)."},{"key":"BF02257778_CR3","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1109\/TCAD.1984.1270075","volume":"3","author":"J. R. Egan","year":"1984","unstructured":"[EL84] Egan, J. R., Liu, C. L.: Bipartite folding and partitioning of a PLA, IEEE Trans. CAD3, 191\u2013199 (1984).","journal-title":"IEEE Trans. CAD"},{"key":"BF02257778_CR4","unstructured":"[GJ] Garey, M. R., Johnson, D. S.: Computers and intractibility. New York, 1979."},{"key":"BF02257778_CR5","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"[GJS76] Garey, M. R., Johnson, P. S., Stockmeyer, L.: Simplified NP-complete graph problems. Theoretical Computer Science1, 237\u2013267 (1976).","journal-title":"Theoretical Computer Science"},{"key":"BF02257778_CR6","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1016\/0196-6774(87)90021-6","volume":"8","author":"David S. Johnson","year":"1987","unstructured":"[Jo87] Johnson, David S.: The NP-completeness column: an ongoing guide. J. Algorithms8, 438\u2013448 (1987).","journal-title":"J. Algorithms"},{"key":"BF02257778_CR7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"[LT79] Lipton, R. J., Tarjan R. E.: A separator theorem for planar graphs. SIAM J. Appl. Mathematics36, 177\u2013189 (1979).","journal-title":"SIAM J. Appl. Mathematics"},{"key":"BF02257778_CR8","unstructured":"[Mi84] Miller, G.: Finding small simple cycle separators for 2-connected planar graphs, Proc. 16th, Anm. ACM Sympos. on Theory of Computing 376\u2013382 (1984)."},{"key":"BF02257778_CR9","doi-asserted-by":"crossref","unstructured":"[M\u00f690] M\u00f6hring, R. H.: Graph problems related to gate matrix layout and PLA folding, In: Tinhofer G. et. al. (eds.) Computing Supplementum 7, Computational graph theory, Springer (1990), 17\u201352.","DOI":"10.1007\/978-3-7091-9076-0_2"},{"key":"BF02257778_CR10","volume-title":"Computational aspects of VLSI","author":"J. D. Ullman","year":"1983","unstructured":"[UL83] Ullman, J. D.: Computational aspects of VLSI. Rockville, USA: Computer Science Press, (1983)."},{"key":"BF02257778_CR11","unstructured":"[WW91] Wagner, D., Wagner, F.: Between min cut and graph bisection, Report B-91-1, Freie Universit\u00e4t Berlin (1991)."}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02257778.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02257778\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02257778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T15:01:48Z","timestamp":1558018908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02257778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,12]]}},"alternative-id":["BF02257778"],"URL":"https:\/\/doi.org\/10.1007\/bf02257778","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}