{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:24:05Z","timestamp":1777667045135,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T00:00:00Z","timestamp":1400112000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s10878-014-9753-x","type":"journal-article","created":{"date-parts":[[2014,5,14]],"date-time":"2014-05-14T11:08:55Z","timestamp":1400065735000},"page":"276-307","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["The $$k$$ k -separator problem: polyhedra, complexity and approximation results"],"prefix":"10.1007","volume":"29","author":[{"given":"Walid","family":"Ben-Ameur","sequence":"first","affiliation":[]},{"given":"Mohamed-Ahmed","family":"Mohamed-Sidi","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9","family":"Neto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,15]]},"reference":[{"key":"9753_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable graphs. J Algorithms 12:308\u2013340","journal-title":"J Algorithms"},{"key":"9753_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(98)00096-1","volume":"89","author":"E Balas","year":"1998","unstructured":"Balas E (1998) Disjunctive programming: properties of the convex hull of feasible points. Discret Appl Math 89:1\u201344","journal-title":"Discret Appl Math"},{"key":"9753_CR3","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s10107-005-0574-7","volume":"103","author":"E Balas","year":"2005","unstructured":"Balas E, de Souza C (2005) The vertex separator problem: a polyhedral investigation. Math Program 103:583\u2013608","journal-title":"Math Program"},{"key":"9753_CR4","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1002\/net.3230190206","volume":"19","author":"E Balas","year":"1989","unstructured":"Balas E, Yu C (1989) On graphs with polynomially solvable maximum-weight clique problem. Networks 19:247\u2013253","journal-title":"Networks"},{"key":"9753_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Ameur W, Mohamed-Sidi M-A., Neto J (2013) The k-separator problem. In: Proceedings of COCOON 2013, Springer LNCS 7936, pp 337\u2013348","DOI":"10.1007\/978-3-642-38768-5_31"},{"key":"9753_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender HL (1993) A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of STOC\u201993, pp 226\u2013234","DOI":"10.1145\/167088.167161"},{"key":"9753_CR7","first-page":"241253","volume":"72","author":"R Boliac","year":"2004","unstructured":"Boliac R, Cameron K, Lozin V (2004) On computing the dissociation number and the induced matching number of bipartite graphs. Ars Combin 72:241253","journal-title":"Ars Combin"},{"key":"9753_CR8","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF01293664","volume":"14","author":"RB Borie","year":"1995","unstructured":"Borie RB (1995) Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica 14:123\u2013137","journal-title":"Algorithmica"},{"key":"9753_CR9","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1137\/S1052623497318682","volume":"9","author":"R Bornd\u00f6rfer","year":"1998","unstructured":"Bornd\u00f6rfer R, Ferreira CE, Martin A (1998) Decomposing matrices into blocks. SIAM J Optim 9:236\u2013269","journal-title":"SIAM J Optim"},{"key":"9753_CR10","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"H Broersma","year":"1999","unstructured":"Broersma H, Kloks T, Kratsch D, M\u00fcller H (1999) Independent sets in asteroidal triple-free graphs. SIAM J Discret Math 12:276\u2013287","journal-title":"SIAM J Discret Math"},{"key":"9753_CR11","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s10107-005-0649-5","volume":"105","author":"K Cameron","year":"2006","unstructured":"Cameron K, Hell P (2006) Independent packings in structured graphs. Math Program Ser B 105:201\u2013213","journal-title":"Math Program Ser B"},{"key":"9753_CR12","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162:439\u2013485","journal-title":"Ann Math"},{"key":"9753_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F Gavril","year":"2000","unstructured":"Gavril F (2000) Maximum weight independent sets and cliques in intersection graphs of filaments. Inf Process Lett 73:181\u2013188","journal-title":"Inf Process Lett"},{"key":"9753_CR14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0166-218X(96)00030-3","volume":"74","author":"O Goldschmidt","year":"1997","unstructured":"Goldschmidt O, Hochbaum D (1997) K-edge subgraphs problems. Discree Appl Math 74:159\u2013169","journal-title":"Discree Appl Math"},{"key":"9753_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib M, McConnell R, Paul C, Viennot L (2000) Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing. Theor Comput Sci 234:59\u201384","journal-title":"Theor Comput Sci"},{"key":"9753_CR16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J Hastad","year":"1999","unstructured":"Hastad J (1999) Clique is hard to approximate within $$n^{1-\\epsilon }$$ n 1 - \u03f5 . Acta Math 182:105\u2013142","journal-title":"Acta Math"},{"key":"9753_CR17","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/0095-8956(85)90050-4","volume":"39","author":"RB Hayard","year":"1985","unstructured":"Hayard RB (1985) Weakly triangulated graphs. J Combin Theory Ser B 39:200\u2013209","journal-title":"J Combin Theory Ser B"},{"key":"9753_CR18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot S, Regev O (2008) Vertex cover might be hard to approximate to within $$2- \\epsilon $$ 2 - \u03f5 . J Comput Syst Sci 74:335\u2013349","journal-title":"J Comput Syst Sci"},{"key":"9753_CR19","doi-asserted-by":"crossref","unstructured":"Kloks T (1994) Treewidth: computations and approximations, vol 842. Lecture Notes in Computer Science, Springer, Berlin","DOI":"10.1007\/BFb0045375"},{"key":"9753_CR20","volume-title":"Combinatorial optimization: theory and algorithms","author":"B Korte","year":"2005","unstructured":"Korte B, Vygen J (2005) Combinatorial optimization: theory and algorithms. Springer, New York"},{"key":"9753_CR21","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"V Lozin","year":"2008","unstructured":"Lozin V, Milanic M (2008) A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J Discret Algorithms 6:595\u2013604","journal-title":"J Discret Algorithms"},{"key":"9753_CR22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.ipl.2003.07.004","volume":"88","author":"V Lozin","year":"2003","unstructured":"Lozin V, Rautenbach D (2003) Some results on graphs without long induced paths. Inform Process Lett 88:167\u2013171","journal-title":"Inform Process Lett"},{"key":"9753_CR23","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G Minty","year":"1980","unstructured":"Minty G (1980) On maximal independent sets of vertices in claw-free graphs. J Combin Theory Ser B 28:284\u2013304","journal-title":"J Combin Theory Ser B"},{"key":"9753_CR24","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1111\/j.1467-9574.2007.00350.x","volume":"61","author":"M Oosten","year":"2007","unstructured":"Oosten M, Rutten J, Spiksma F (2007) Disconnecting graphs by removing vertices: a polyhedral approach. Stat Neerl 61:35\u201360","journal-title":"Stat Neerl"},{"key":"9753_CR25","doi-asserted-by":"crossref","first-page":"1352","DOI":"10.1016\/j.dam.2011.04.023","volume":"159","author":"Y Orlovich","year":"2011","unstructured":"Orlovich Y, Dolgui A, Finke G, Gordon V, Werner F (2011) The complexity of dissociation set problems in graphs. Discret Appl Math 159:1352\u20131366","journal-title":"Discret Appl Math"},{"key":"9753_CR26","first-page":"285309","volume":"29","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou CH, Yannakakis M (1982) The complexity of restricted spanning tree problems. J Assoc Comput Mach 29:285309","journal-title":"J Assoc Comput Mach"},{"key":"9753_CR27","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi N (1980) Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discret Math 29:53\u201376","journal-title":"Discret Math"},{"key":"9753_CR28","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin"},{"key":"9753_CR29","first-page":"192","volume-title":"Approximation algorithms for NP-hard problems","author":"D Shmoys","year":"1997","unstructured":"Shmoys D (1997) Cut problems and their application to divide-and-conquer. In: Dorit SH (ed) Approximation algorithms for NP-hard problems. PWS, Boston, pp 192\u2013235"},{"key":"9753_CR30","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0166-218X(93)E0161-Q","volume":"59","author":"JP Spinrad","year":"1995","unstructured":"Spinrad JP, Sritharan R (1995) Algorithms for weakly triangulated graphs. Discret Appl Math 59:181\u2013191","journal-title":"Discret Appl Math"},{"key":"9753_CR31","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle JA, Proskurowski A (1997) Algorithms for vertex partitioning problems on partial k-trees. SIAM J Discret Math 10:529\u2013550","journal-title":"SIAM J Discret Math"},{"key":"9753_CR32","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/s101070100262","volume":"91","author":"D Williamson","year":"2002","unstructured":"Williamson D (2002) The primal-dual method for approximation algorithms. Math Program Ser B 91:447\u2013478","journal-title":"Math Program Ser B"},{"key":"9753_CR33","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis M (1981) Node-deletion problems on bipartite graphs. SIAM J Comput 10:310\u2013327","journal-title":"SIAM J Comput"},{"key":"9753_CR34","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput 3:103\u2013138","journal-title":"Theory Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9753-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9753-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9753-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T12:46:52Z","timestamp":1565441212000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9753-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,15]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9753"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9753-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,15]]}}}