Eldén, Lars Multiway spectral graph partitioning: cut functions, Cheeger inequalities, and a simple algorithm. (English) Zbl 07791521 SIAM J. Matrix Anal. Appl. 45, No. 1, 112-133 (2024). Reviewer: Vladimír Lacko (Košice) MSC: 68R10 05C50 05C70 05C85 90C35 PDFBibTeX XMLCite \textit{L. Eldén}, SIAM J. Matrix Anal. Appl. 45, No. 1, 112--133 (2024; Zbl 07791521) Full Text: DOI arXiv
Bloch-Hansen, Andrew; Samei, Nasim; Solis-Oba, Roberto A local search approximation algorithm for the multiway cut problem. (English) Zbl 07721324 Discrete Appl. Math. 338, 8-21 (2023). MSC: 90C35 90C57 PDFBibTeX XMLCite \textit{A. Bloch-Hansen} et al., Discrete Appl. Math. 338, 8--21 (2023; Zbl 07721324) Full Text: DOI
Chandrasekaran, Karthekeyan; Wang, Weihang \(\ell_p\)-norm multiway cut. (English) Zbl 07572798 Algorithmica 84, No. 9, 2667-2701 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{K. Chandrasekaran} and \textit{W. Wang}, Algorithmica 84, No. 9, 2667--2701 (2022; Zbl 07572798) Full Text: DOI arXiv
Bergougnoux, Benjamin; Papadopoulos, Charis; Telle, Jan Arne Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. (English) Zbl 07517140 Algorithmica 84, No. 5, 1385-1417 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{B. Bergougnoux} et al., Algorithmica 84, No. 5, 1385--1417 (2022; Zbl 07517140) Full Text: DOI arXiv
Cohen-Addad, Vincent; de Verdière, Éric Colin; Marx, Dániel; de Mesmay, Arnaud Almost tight lower bounds for hard cutting problems in embedded graphs. (English) Zbl 1499.68264 J. ACM 68, No. 4, Paper No. 30, 26 p. (2021). MSC: 68R10 05C10 68Q17 68Q27 PDFBibTeX XMLCite \textit{V. Cohen-Addad} et al., J. ACM 68, No. 4, Paper No. 30, 26 p. (2021; Zbl 1499.68264) Full Text: DOI
Shim, Sangho; Bandi, Chaithanya; Chopra, Sunil On the (near) optimality of extended formulations for multi-way cut in social networks. (English) Zbl 1485.90071 Optim. Eng. 22, No. 3, 1557-1588 (2021). MSC: 90C10 90C35 91D30 PDFBibTeX XMLCite \textit{S. Shim} et al., Optim. Eng. 22, No. 3, 1557--1588 (2021; Zbl 1485.90071) Full Text: DOI
Jansen, Bart M. P.; Pilipczuk, Marcin L.; van Leeuwen, Erik Jan A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs. (English) Zbl 1510.68077 SIAM J. Discrete Math. 35, No. 4, 2387-2429 (2021). MSC: 68R10 68Q25 68W40 05C10 05C85 PDFBibTeX XMLCite \textit{B. M. P. Jansen} et al., SIAM J. Discrete Math. 35, No. 4, 2387--2429 (2021; Zbl 1510.68077) Full Text: DOI arXiv
Buchbinder, Niv; Schwartz, Roy; Weizman, Baruch Simplex transformations and the multiway cut problem. (English) Zbl 1522.05465 Math. Oper. Res. 46, No. 2, 757-771 (2021). MSC: 05C85 05C70 68W25 90C35 PDFBibTeX XMLCite \textit{N. Buchbinder} et al., Math. Oper. Res. 46, No. 2, 757--771 (2021; Zbl 1522.05465) Full Text: DOI
Miao, Dongjing; Li, Jianzhong; Cai, Zhipeng Maximum reachability preserved graph cut. (English) Zbl 1455.68145 Theor. Comput. Sci. 840, 187-198 (2020). MSC: 68R10 68Q17 68Q25 PDFBibTeX XMLCite \textit{D. Miao} et al., Theor. Comput. Sci. 840, 187--198 (2020; Zbl 1455.68145) Full Text: DOI
Bérczi, Kristóf; Chandrasekaran, Karthekeyan; Király, Tamás; Madan, Vivek Improving the integrality gap for multiway cut. (English) Zbl 1450.90038 Math. Program. 183, No. 1-2 (B), 171-193 (2020). MSC: 90C27 PDFBibTeX XMLCite \textit{K. Bérczi} et al., Math. Program. 183, No. 1--2 (B), 171--193 (2020; Zbl 1450.90038) Full Text: DOI Link
Chandrasekaran, Karthekeyan; Mnich, Matthias; Mozaffari, Sahand Odd multiway cut in directed acyclic graphs. (English) Zbl 1443.68123 SIAM J. Discrete Math. 34, No. 2, 1385-1408 (2020). MSC: 68R10 68Q27 68W25 PDFBibTeX XMLCite \textit{K. Chandrasekaran} et al., SIAM J. Discrete Math. 34, No. 2, 1385--1408 (2020; Zbl 1443.68123) Full Text: DOI
Papadopoulos, Charis; Tzimas, Spyridon Subset feedback vertex set on graphs of bounded independent set size. (English) Zbl 1435.68244 Theor. Comput. Sci. 814, 177-188 (2020). MSC: 68R10 05C69 05C85 68Q17 68Q25 68W40 PDFBibTeX XMLCite \textit{C. Papadopoulos} and \textit{S. Tzimas}, Theor. Comput. Sci. 814, 177--188 (2020; Zbl 1435.68244) Full Text: DOI Link
Zschoche, Philipp; Fluschnik, Till; Molter, Hendrik; Niedermeier, Rolf The complexity of finding small separators in temporal graphs. (English) Zbl 1436.68265 J. Comput. Syst. Sci. 107, 72-92 (2020). MSC: 68R10 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{P. Zschoche} et al., J. Comput. Syst. Sci. 107, 72--92 (2020; Zbl 1436.68265) Full Text: DOI Link
Buchbinder, Niv; Schwartz, Roy; Weizman, Baruch A simple algorithm for the multiway cut problem. (English) Zbl 1476.90336 Oper. Res. Lett. 47, No. 6, 587-593 (2019). MSC: 90C35 05C22 05C40 PDFBibTeX XMLCite \textit{N. Buchbinder} et al., Oper. Res. Lett. 47, No. 6, 587--593 (2019; Zbl 1476.90336) Full Text: DOI
Hirai, Hiroshi A dual descent algorithm for node-capacitated multiflow problems and its applications. (English) Zbl 1457.90026 ACM Trans. Algorithms 15, No. 1, Article No. 15, 24 p. (2019). MSC: 90B10 68W25 PDFBibTeX XMLCite \textit{H. Hirai}, ACM Trans. Algorithms 15, No. 1, Article No. 15, 24 p. (2019; Zbl 1457.90026) Full Text: DOI arXiv
Buchbinder, Niv; Naor, Joseph; Schwartz, Roy Simplex partitioning via exponential clocks and the multiway-cut problem. (English) Zbl 1397.68220 SIAM J. Comput. 47, No. 4, 1463-1482 (2018). MSC: 68W25 05C70 05C85 68U05 68W20 PDFBibTeX XMLCite \textit{N. Buchbinder} et al., SIAM J. Comput. 47, No. 4, 1463--1482 (2018; Zbl 1397.68220) Full Text: DOI
Chitnis, Rajesh; Fomin, Fedor V.; Lokshtanov, Daniel; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket Faster exact algorithms for some terminal set problems. (English) Zbl 1371.05283 J. Comput. Syst. Sci. 88, 195-207 (2017). MSC: 05C85 68Q25 PDFBibTeX XMLCite \textit{R. Chitnis} et al., J. Comput. Syst. Sci. 88, 195--207 (2017; Zbl 1371.05283) Full Text: DOI Link
Kim, Eun Jung; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M. Parameterized algorithms for min-max multiway cut and list digraph homomorphism. (English) Zbl 1370.68131 J. Comput. Syst. Sci. 86, 191-206 (2017). MSC: 68Q25 05C85 PDFBibTeX XMLCite \textit{E. J. Kim} et al., J. Comput. Syst. Sci. 86, 191--206 (2017; Zbl 1370.68131) Full Text: DOI Link
van Bevern, René; Bredereck, Robert; Chopin, Morgan; Hartung, Sepp; Hüffner, Falk; Nichterlein, André; Suchý, Ondřej Fixed-parameter algorithms for DAG partitioning. (English) Zbl 1355.05204 Discrete Appl. Math. 220, 134-160 (2017). MSC: 05C70 05C85 05C82 05C12 PDFBibTeX XMLCite \textit{R. van Bevern} et al., Discrete Appl. Math. 220, 134--160 (2017; Zbl 1355.05204) Full Text: DOI arXiv
Kanj, Iyad; Lin, Guohui; Liu, Tian; Tong, Weitian; Xia, Ge; Xu, Jinhui; Yang, Boting; Zhang, Fenghui; Zhang, Peng; Zhu, Binhai Improved parameterized and exact algorithms for cut problems on trees. (English) Zbl 1333.05293 Theor. Comput. Sci. 607, Part 3, 455-470 (2015). MSC: 05C85 05C05 05C70 68Q25 90C35 PDFBibTeX XMLCite \textit{I. Kanj} et al., Theor. Comput. Sci. 607, Part 3, 455--470 (2015; Zbl 1333.05293) Full Text: DOI
Liu, Hong; Zhang, Peng On the generalized multiway cut in trees problem. (English) Zbl 1286.90158 J. Comb. Optim. 27, No. 1, 65-77 (2014). MSC: 90C35 90C27 90C59 PDFBibTeX XMLCite \textit{H. Liu} and \textit{P. Zhang}, J. Comb. Optim. 27, No. 1, 65--77 (2014; Zbl 1286.90158) Full Text: DOI
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry On multiway cut parameterized above lower bounds. (English) Zbl 1322.68098 ACM Trans. Comput. Theory 5, No. 1, Article No. 3, 11 p. (2013). MSC: 68Q25 05C70 05C85 68Q17 90C05 PDFBibTeX XMLCite \textit{M. Cygan} et al., ACM Trans. Comput. Theory 5, No. 1, Article No. 3, 11 p. (2013; Zbl 1322.68098) Full Text: DOI arXiv
Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Marx, Dániel Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. (English) Zbl 1312.68097 SIAM J. Comput. 42, No. 4, 1674-1696 (2013). MSC: 68Q25 05C20 05C40 05C85 PDFBibTeX XMLCite \textit{R. Chitnis} et al., SIAM J. Comput. 42, No. 4, 1674--1696 (2013; Zbl 1312.68097) Full Text: DOI arXiv
Anshelevich, Elliot; Caskurlu, Bugra; Hate, Ameya Strategic multiway cut and multicut games. (English) Zbl 1260.90046 Theory Comput. Syst. 52, No. 2, 200-220 (2013). MSC: 90B15 91A80 PDFBibTeX XMLCite \textit{E. Anshelevich} et al., Theory Comput. Syst. 52, No. 2, 200--220 (2013; Zbl 1260.90046) Full Text: DOI
Dean, Brian C.; Griffis, Adam; Parekh, Ojas; Whitley, Adam Approximation algorithms for \(k\)-hurdle problems. (English) Zbl 1213.68436 Algorithmica 59, No. 1, 81-93 (2011). MSC: 68R10 68W25 PDFBibTeX XMLCite \textit{B. C. Dean} et al., Algorithmica 59, No. 1, 81--93 (2011; Zbl 1213.68436) Full Text: DOI
Karloff, Howard; Khot, Subhash; Mehta, Aranyak; Rabani, Yuval On earthmover distance, metric labeling, and 0-extension. (English) Zbl 1200.68121 SIAM J. Comput. 39, No. 2, 371-387 (2009). MSC: 68Q17 68W25 PDFBibTeX XMLCite \textit{H. Karloff} et al., SIAM J. Comput. 39, No. 2, 371--387 (2009; Zbl 1200.68121) Full Text: DOI
Chen, Jianer; Liu, Yang; Lu, Songjian An improved parameterized algorithm for the minimum node multiway cut problem. (English) Zbl 1194.68168 Algorithmica 55, No. 1, 1-13 (2009). MSC: 68R10 68W05 PDFBibTeX XMLCite \textit{J. Chen} et al., Algorithmica 55, No. 1, 1--13 (2009; Zbl 1194.68168) Full Text: DOI
Avidor, Adi; Langberg, Michael The multi-multiway cut problem. (English) Zbl 1115.68171 Theor. Comput. Sci. 377, No. 1-3, 35-42 (2007). MSC: 68W25 90C05 PDFBibTeX XMLCite \textit{A. Avidor} and \textit{M. Langberg}, Theor. Comput. Sci. 377, No. 1--3, 35--42 (2007; Zbl 1115.68171) Full Text: DOI
Kamidoi, Yoko; Yoshida, Noriyoshi; Nagamochi, Hiroshi A deterministic algorithm for finding all minimum \(k\)-way cuts. (English) Zbl 1124.05083 SIAM J. Comput. 36, No. 5, 1329-1341 (2006). MSC: 05C85 68R10 68W05 PDFBibTeX XMLCite \textit{Y. Kamidoi} et al., SIAM J. Comput. 36, No. 5, 1329--1341 (2006; Zbl 1124.05083) Full Text: DOI
Chekuri, Chandra; Guha, Sudipto; Naor, Joseph The Steiner \(k\)-cut problem. (English) Zbl 1107.68121 SIAM J. Discrete Math. 20, No. 1, 261-271 (2006). MSC: 68W25 68Q25 90C27 90C59 PDFBibTeX XMLCite \textit{C. Chekuri} et al., SIAM J. Discrete Math. 20, No. 1, 261--271 (2006; Zbl 1107.68121) Full Text: DOI
Khachiyan, L.; Boros, E.; Elbassioni, K.; Gurvich, V.; Makino, K. On the complexity of some enumeration problems for matroids. (English) Zbl 1104.05017 SIAM J. Discrete Math. 19, No. 4, 966-984 (2006). MSC: 05B35 05A99 68Q25 PDFBibTeX XMLCite \textit{L. Khachiyan} et al., SIAM J. Discrete Math. 19, No. 4, 966--984 (2006; Zbl 1104.05017) Full Text: DOI
Marx, Dániel Parameterized graph separation problems. (English) Zbl 1086.68104 Theor. Comput. Sci. 351, No. 3, 394-406 (2006). MSC: 68R10 68Q25 05C85 PDFBibTeX XMLCite \textit{D. Marx}, Theor. Comput. Sci. 351, No. 3, 394--406 (2006; Zbl 1086.68104) Full Text: DOI
Zhao, Liang; Nagamochi, Hiroshi; Ibaraki, Toshihide Greedy splitting algorithms for approximating multiway partition problems. (English) Zbl 1177.90403 Math. Program. 102, No. 1 (A), 167-183 (2005). MSC: 90C35 90C57 PDFBibTeX XMLCite \textit{L. Zhao} et al., Math. Program. 102, No. 1 (A), 167--183 (2005; Zbl 1177.90403) Full Text: DOI
Costa, Marie-Christine; Létocart, Lucas; Roupin, Frédéric Minimal multicut and maximal integer multiflow: a survey. (English) Zbl 1132.90306 Eur. J. Oper. Res. 162, No. 1, 55-69 (2005). MSC: 90B10 90C10 90C35 90C60 PDFBibTeX XMLCite \textit{M.-C. Costa} et al., Eur. J. Oper. Res. 162, No. 1, 55--69 (2005; Zbl 1132.90306) Full Text: DOI
Karger, David R.; Klein, Philip; Stein, Cliff; Thorup, Mikkel; Young, Neal E. Rounding algorithms for a geometric embedding of minimum multiway cut. (English) Zbl 1082.90149 Math. Oper. Res. 29, No. 3, 436-461 (2004). MSC: 90C59 05C40 68Q25 68R10 90C35 PDFBibTeX XMLCite \textit{D. R. Karger} et al., Math. Oper. Res. 29, No. 3, 436--461 (2004; Zbl 1082.90149) Full Text: DOI arXiv
Karzanov, Alexander V. Hard cases of the multifacility location problem. (English) Zbl 1077.90036 Discrete Appl. Math. 143, No. 1-3, 368-373 (2004). MSC: 90B80 05C12 90C27 PDFBibTeX XMLCite \textit{A. V. Karzanov}, Discrete Appl. Math. 143, No. 1--3, 368--373 (2004; Zbl 1077.90036) Full Text: DOI
Zhao, Liang; Nagamochi, Hiroshi; Ibaraki, Toshihide On generalized greedy splitting algorithms for multiway partition problems. (English) Zbl 1103.68145 Discrete Appl. Math. 143, No. 1-3, 130-143 (2004). MSC: 68W25 05A18 PDFBibTeX XMLCite \textit{L. Zhao} et al., Discrete Appl. Math. 143, No. 1--3, 130--143 (2004; Zbl 1103.68145) Full Text: DOI
Naor, Joseph; Zosin, Leonid A 2-approximation algorithm for the directed multiway cut problem. (English) Zbl 1052.68103 SIAM J. Comput. 31, No. 2, 477-482 (2001). MSC: 68R10 05C85 68W10 68Q25 90C27 90C35 68W25 PDFBibTeX XMLCite \textit{J. Naor} and \textit{L. Zosin}, SIAM J. Comput. 31, No. 2, 477--482 (2001; Zbl 1052.68103) Full Text: DOI
Porter, Thom; Yang, Bing Graph partitions. II. (English) Zbl 0988.05050 J. Comb. Math. Comb. Comput. 37, 149-158 (2001). Reviewer: László A.Székely (Columbia/South Carolina) MSC: 05C35 05C15 PDFBibTeX XMLCite \textit{T. Porter} and \textit{B. Yang}, J. Comb. Math. Comb. Comput. 37, 149--158 (2001; Zbl 0988.05050)
Călinescu, Gruia; Karloff, Howard; Rabani, Yuval An improved approximation algorithm of MULTIWAY CUT. (English) Zbl 0986.90043 J. Comput. Syst. Sci. 60, No. 3, 564-574 (2000). MSC: 90C27 90C05 68R10 68W25 PDFBibTeX XMLCite \textit{G. Călinescu} et al., J. Comput. Syst. Sci. 60, No. 3, 564--574 (2000; Zbl 0986.90043) Full Text: DOI
Erdős, Péter L.; Frank, András; Székely, László Minimum multiway cuts in trees. (English) Zbl 0910.90261 Discrete Appl. Math. 87, No. 1-3, 67-75 (1998). MSC: 90C35 05C85 05C05 PDFBibTeX XMLCite \textit{P. L. Erdős} et al., Discrete Appl. Math. 87, No. 1--3, 67--75 (1998; Zbl 0910.90261) Full Text: DOI Link
Klein, Philip; Rao, Satish; Agrawal, Ajit; Ravi, R. An approximate max-flow min-cut relation for undirected multicommodity flow, with applications. (English) Zbl 0837.68045 Combinatorica 15, No. 2, 187-202 (1995). MSC: 68Q25 68R10 90C08 90C27 PDFBibTeX XMLCite \textit{P. Klein} et al., Combinatorica 15, No. 2, 187--202 (1995; Zbl 0837.68045) Full Text: DOI
Erdös, Péter L.; Székely, László A. On weighted multiway cuts in trees. (English) Zbl 0805.05016 Math. Program. 65, No. 1 (A), 93-105 (1994). Reviewer: S.F.Kapoor (Kalamazoo) MSC: 05C05 90C39 90C35 05C70 90C27 PDFBibTeX XMLCite \textit{P. L. Erdös} and \textit{L. A. Székely}, Math. Program. 65, No. 1 (A), 93--105 (1994; Zbl 0805.05016) Full Text: DOI
Erdös, Péter L.; Székely, László A. Evolutionary trees: An integer multicommodity max-flow – min-cut theorem. (English) Zbl 0773.05047 Adv. Appl. Math. 13, No. 4, 375-389 (1992). MSC: 05C15 05C05 PDFBibTeX XMLCite \textit{P. L. Erdös} and \textit{L. A. Székely}, Adv. Appl. Math. 13, No. 4, 375--389 (1992; Zbl 0773.05047) Full Text: DOI