Search results for "multicut"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
129	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	J. ACM	2009	DBLP DOI BibTeX RDF	Directed multicut, hardness of approximation, sparsest cut
129	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
129	Julia Chuzhoy, Sanjeev Khanna	Hardness of cut problems in directed graphs.	STOC	2006	DBLP DOI BibTeX RDF	directed multicut, hardness of approximation, sparsest cut
108	Daniel Golovin, Viswanath Nagarajan, Mohit Singh	Approximating the k-multicut problem.	SODA	2006	DBLP DOI BibTeX RDF
108	Michael E. Saks, Alex Samorodnitsky, Leonid Zosin	A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C20, 90C35, 90B10
91	Kenji Obata	Approximate max-integral-flow/min-multicut theorems.	STOC	2004	DBLP DOI BibTeX RDF
81	Peng Zhang 0008	Approximating Generalized Multicut on Trees.	CiE	2007	DBLP DOI BibTeX RDF	Generalized Multicut, Approximation Algorithm, Combinatorial Optimization, Tree
69	Asaf Levin, Danny Segev	Partial Multicuts in Trees.	WAOA	2005	DBLP DOI BibTeX RDF
69	Yana Kortsarts, Guy Kortsarz, Zeev Nutov	Approximation Algorithm for Directed Multicuts.	WAOA	2004	DBLP DOI BibTeX RDF
69	Adi Avidor, Michael Langberg	The Multi-multiway Cut Problem.	SWAT	2004	DBLP DOI BibTeX RDF
69	Gruia Calinescu, Cristina G. Fernandes, Bruce A. Reed	Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width.	IPCO	1998	DBLP DOI BibTeX RDF
56	Dániel Marx, Igor Razgon	Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem.	ESA	2009	DBLP DOI BibTeX RDF
56	Xiucui Guan, Jie Su	Further Research on Node Based Bottleneck Improvement Problem for Multicut.	ICIC (1)	2006	DBLP DOI BibTeX RDF
56	Garima Batra, Naveen Garg 0001, Garima Gupta	Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut.	ESA	2005	DBLP DOI BibTeX RDF
56	Jan von Plato	A proof of Gentzen's Hauptsatz without multicut.	Arch. Math. Log.	2001	DBLP DOI BibTeX RDF
56	Dimitris Bertsimas, Chung-Piaw Teo, Rakesh Vohra	Nonlinear Formulations and Improved Randomized Approximation Algorithms for Multicut Problems.	IPCO	1995	DBLP DOI BibTeX RDF
56	Bo Yu 0001, Joseph Cheriyan	Approximation Algorithms for Feasible Cut and Multicut Problems.	ESA	1995	DBLP DOI BibTeX RDF
43	Jørgen Bang-Jensen, Anders Yeo	The complexity of multicut and mixed multicut problems in (di)graphs.	Theor. Comput. Sci.	2014	DBLP DOI BibTeX RDF
43	Nicolas Bousquet	Hitting sets : VC-dimension and Multicut. (Hitting sets : VC-dimension et Multicut).		2013	RDF
42	Mingyu Xiao 0001	Algorithms for Multiterminal Cuts.	CSR	2008	DBLP DOI BibTeX RDF	Multiterminal Cut, Graph Algorithm, Fixed Parameter Tractability, Multicut
42	Amit Agarwal, Noga Alon, Moses Charikar	Improved approximation for directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	directed multicut, directed sparsest cut, approximation algorithm, linear programming relaxation
42	Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev	O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.	STOC	2005	DBLP DOI BibTeX RDF	directed balanced separator, directed sparsest cut, min 2CNF deletion, min UnCut, min multicut
39	Cédric Bentz	Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity.	4OR	2008	DBLP DOI BibTeX RDF	MSC Classification 05C85, 90C27, 68Q17
39	Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001	On the Hardness of Approximating Multicut and Sparsest-Cut.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
39	Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, Johannes Uhlmann	Complexity and Exact Algorithms for Multicut.	SOFSEM	2006	DBLP DOI BibTeX RDF
39	Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001	On the Hardness of Approximating Multicut and Sparsest-Cut.	CCC	2005	DBLP DOI BibTeX RDF
39	Anupam Gupta 0001	Improved results for directed multicut.	SODA	2003	DBLP BibTeX RDF
35	Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy	Approximation algorithms for labeling hierarchical taxonomies.	SODA	2008	DBLP BibTeX RDF
35	Brian C. Dean, Adam Griffis, Adam A. Whitley	Approximation Algorithms for k-Hurdle Problems.	LATIN	2008	DBLP DOI BibTeX RDF
35	Roee Engelberg, Jochen Könemann, Stefano Leonardi 0001, Joseph Naor	Cut Problems in Graphs with a Budget Constraint.	LATIN	2006	DBLP DOI BibTeX RDF
35	Joseph Cheriyan, Howard J. Karloff, Yuval Rabani	Approximating Directed Multicuts.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C20, 90C27, 05C85, 68W25
25	Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino	Generating Cut Conjunctions in Graphs and Related Problems.	Algorithmica	2008	DBLP DOI BibTeX RDF	Cut conjunction, Cut generation, Graph, Matroid, Multicut
25	Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell	Eliminating Cycles in the Discrete Torus.	Algorithmica	2008	DBLP DOI BibTeX RDF	Discrete torus, Foam, Tiling, Multicut
25	Ojas Parekh, Danny Segev	Path Hitting in Acyclic Graphs.	Algorithmica	2008	DBLP DOI BibTeX RDF	Edge cover, Tree augmentation, Tree multicut, Approximation algorithms, Linear programming, Primal-dual, Edge dominating set
25	Guy Even, Joseph Naor, Satish Rao, Baruch Schieber	Divide-and-conquer approximation algorithms via spreading metrics.	J. ACM	2000	DBLP DOI BibTeX RDF	feedback set, spreading metrics, approximation algorithms, divide and conquer, multicut, linear arrangement
21	Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao, Bjoern Andres	Cut Facets and Cube Facets of Lifted Multicut Polytopes.	CoRR	2024	DBLP DOI BibTeX RDF
21	Zhimeng Xin, Tongwei Lu, Yuzhou Li, Xinge You	MultiCut-MultiMix: a two-level data augmentation method for detecting small and densely distributed objects in large-size images.	Vis. Comput.	2024	DBLP DOI BibTeX RDF
21	Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale	Parameterized complexity of multicut in weighted trees.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
21	George Osipov, Marcin Pilipczuk	Directed Symmetric Multicut is W[1]-hard.	CoRR	2023	DBLP DOI BibTeX RDF
21	Jacob Focke, Florian Hörsch, Shaohua Li 0005, Dániel Marx	Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.	CoRR	2023	DBLP DOI BibTeX RDF
21	Joaquim Dias Garcia, Iago Leal, Raphael Chabar, Mario Veiga Pereira	A Multicut Approach to Compute Upper Bounds for Risk-Averse SDDP.	CoRR	2023	DBLP DOI BibTeX RDF
21	Ahmed Abbas, Paul Swoboda	ClusterFuG: Clustering Fully connected Graphs by Multicut.	CoRR	2023	DBLP DOI BibTeX RDF
21	Xavier Blanchot, François Clautiaux, Boris Detienne, Aurélien Froger, Manuel Ruiz	The Benders by batch algorithm: Design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs.	Eur. J. Oper. Res.	2023	DBLP DOI BibTeX RDF
21	Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge	Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation.	SODA	2023	DBLP DOI BibTeX RDF
21	Siyue Zhang, Yiyong Xiao, Xinhao Cui, Ruiyi Yang	A Linear Programming Approach for Maximum Integral Multiflow and Minimum Multicut Problems in Unrestricted Network.	ICAC	2023	DBLP DOI BibTeX RDF
21	Tobias Friedrich 0001, Davis Issac, Nikhil Kumar 0001, Nadym Mallek, Ziena Zeif	Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth.	STOC	2023	DBLP DOI BibTeX RDF
21	Ahmed Abbas, Paul Swoboda	ClusterFuG: Clustering Fully connected Graphs by Multicut.	ICML	2023	DBLP BibTeX RDF
21	Kalun Ho	Learning deep visual features for Minimum Cost Multicut Problem.		2023	RDF
21	Ilias Mitrai, Prodromos Daoutidis	A multicut generalized benders decomposition approach for the integration of process operations and dynamic optimization for continuous systems.	Comput. Chem. Eng.	2022	DBLP DOI BibTeX RDF
21	Magnus Wahlström	Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems.	ACM Trans. Algorithms	2022	DBLP DOI BibTeX RDF
21	Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge	Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation.	CoRR	2022	DBLP DOI BibTeX RDF
21	Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale	Parameterized Complexity of Weighted Multicut in Trees.	CoRR	2022	DBLP DOI BibTeX RDF
21	Eduard Eiben, Clément Rambaud, Magnus Wahlström	On the parameterized complexity of symmetric directed multicut.	CoRR	2022	DBLP DOI BibTeX RDF
21	Tobias Friedrich 0001, Davis Issac, Nikhil Kumar 0001, Nadym Mallek, Ziena Zeif	Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth.	CoRR	2022	DBLP DOI BibTeX RDF
21	Xiaofei Liu, Weidong Li 0002	Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties.	J. Comb. Optim.	2022	DBLP DOI BibTeX RDF
21	Kunanon Burathep, Jittat Fakcharoenphol	An Approximation Algorithm for the Vertex Multicut on Trees with an Application to the Tracking Paths Problem.	JCSSE	2022	DBLP DOI BibTeX RDF
21	Xiaofei Liu, Weidong Li	An Approximation Algorithm for the B-prize-collecting Multicut Problem in Trees.	TAMC	2022	DBLP DOI BibTeX RDF
21	Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale	Parameterized Complexity of Weighted Multicut in Trees.	WG	2022	DBLP DOI BibTeX RDF
21	Steffen Jung 0001, Sebastian Ziegler, Amirhossein Kardoost, Margret Keuper	Optimizing Edge Detection for Image Segmentation with Multicut Penalties.	GCPR	2022	DBLP DOI BibTeX RDF
21	Ahmed Abbas, Paul Swoboda	RAMA: A Rapid Multicut Algorithm on GPU.	CVPR	2022	DBLP DOI BibTeX RDF
21	Duy M. H. Nguyen, Roberto Henschel, Bodo Rosenhahn, Daniel Sonntag, Paul Swoboda	LMGP: Lifted Multicut Meets Geometry Projections for Multi-Camera Multi-Object Tracking.	CVPR	2022	DBLP DOI BibTeX RDF
21	Eduard Eiben, Clément Rambaud, Magnus Wahlström	On the Parameterized Complexity of Symmetric Directed Multicut.	IPEC	2022	DBLP DOI BibTeX RDF
21	Andrea Hornáková	Lifted edges as connectivity priors for multicut and disjoint paths.		2022	RDF
21	Chenfei Hou, Suogang Gao, Wen Liu 0009, Weili Wu 0001, Ding-Zhu Du, Bo Hou	An approximation algorithm for the submodular multicut problem in trees with linear penalties.	Optim. Lett.	2021	DBLP DOI BibTeX RDF
21	Michelle Bandarra, Vincent Guigues	Single cut and multicut stochastic dual dynamic programming with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments.	Comput. Manag. Sci.	2021	DBLP DOI BibTeX RDF
21	Duy M. H. Nguyen, Roberto Henschel, Bodo Rosenhahn, Daniel Sonntag, Paul Swoboda	LMGP: Lifted Multicut Meets Geometry Projections for Multi-Camera Multi-Object Tracking.	CoRR	2021	DBLP BibTeX RDF
21	Ahmed Abbas, Paul Swoboda	RAMA: A Rapid Multicut Algorithm on GPU.	CoRR	2021	DBLP BibTeX RDF
21	Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover	On the Dominant of the Multicut Polytope.	CoRR	2021	DBLP BibTeX RDF
21	Steffen Jung 0001, Sebastian Ziegler, Amirhossein Kardoost, Margret Keuper	Optimizing Edge Detection for Image Segmentation with Multicut Penalties.	CoRR	2021	DBLP BibTeX RDF
21	Xin Hou, Wen Liu 0009, Bo Hou	An approximation algorithm for the k-prize-collecting multicut on a tree problem.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
21	Cédric Bentz, Pierre Le Bodic	Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
21	Magnus Wahlström	On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems.	CoRR	2020	DBLP BibTeX RDF
21	Tien Mai, Andrea Lodi 0001	A multicut outer-approximation approach for competitive facility location under random utilities.	Eur. J. Oper. Res.	2020	DBLP DOI BibTeX RDF
21	Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote	Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane.	Discret. Comput. Geom.	2020	DBLP DOI BibTeX RDF
21	Magnus Wahlström	On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems.	ICALP	2020	DBLP DOI BibTeX RDF
21	Jan-Hendrik Lange, Björn Andres	On the Lifted Multicut Polytope for Trees.	GCPR	2020	DBLP DOI BibTeX RDF
21	Kalun Ho, Amirhossein Kardoost, Franz-Josef Pfreundt, Janis Keuper, Margret Keuper	A Two-Stage Minimum Cost Multicut Approach to Self-supervised Multiple Person Tracking.	ACCV (2)	2020	DBLP DOI BibTeX RDF
21	Jan-Hendrik Lange	Multicut optimization guarantees & geometry of lifted multicuts.		2020	RDF
21	Saba Ahmadi, Sainyam Galhotra, Samir Khuller, Barna Saha, Roy Schwartz 0002	Min-Max Correlation Clustering via MultiCut.	CoRR	2019	DBLP BibTeX RDF
21	Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote	Geometric Multicut.	CoRR	2019	DBLP BibTeX RDF
21	Saba Ahmadi, Samir Khuller, Barna Saha	Min-Max Correlation Clustering via MultiCut.	IPCO	2019	DBLP DOI BibTeX RDF
21	Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote	Geometric Multicut.	ICALP	2019	DBLP DOI BibTeX RDF
21	Jan-Hendrik Lange, Bjoern Andres, Paul Swoboda	Combinatorial Persistency Criteria for Multicut and Max-Cut.	CVPR	2019	DBLP BibTeX RDF
21	Xiaofei Liu, Weidong Li 0002	A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties.	AAIM	2019	DBLP DOI BibTeX RDF
21	Evgeny Levinkov	Generalizations of the Multicut Problem for Computer Vision.		2019	RDF
21	Alan Kuhnle, Victoria G. Crawford, My T. Thai	Network Resilience and the Length-Bounded Multicut Problem: Reaching the Dynamic Billion-Scale with Guarantees.	Proc. ACM Meas. Anal. Comput. Syst.	2018	DBLP DOI BibTeX RDF
21	Fatemeh Mohammadi, Eduardo Sáenz-de-Cabezón, Henry P. Wynn	Efficient multicut enumeration of k-out-of-n: F and consecutive k-out-of-n: F systems.	Pattern Recognit. Lett.	2018	DBLP DOI BibTeX RDF
21	Ya Su	Segmentation and reconstruction of DCT images based on lifted multicut.	EURASIP J. Image Video Process.	2018	DBLP DOI BibTeX RDF
21	Marcin Pilipczuk, Magnus Wahlström	Directed Multicut is W[1]-hard, Even for Four Terminal Pairs.	ACM Trans. Comput. Theory	2018	DBLP DOI BibTeX RDF
21	Nicolas Bousquet, Jean Daligault, Stéphan Thomassé	Multicut Is FPT.	SIAM J. Comput.	2018	DBLP DOI BibTeX RDF
21	Alan Kuhnle, Victoria G. Crawford, My T. Thai	Network Resilience and the Length-Bounded Multicut Problem: Reaching the Dynamic Billion-Scale with Guarantees.	SIGMETRICS (Abstracts)	2018	DBLP DOI BibTeX RDF
21	Amirhossein Kardoost, Margret Keuper	Solving Minimum Cost Lifted Multicut Problems by Node Agglomeration.	ACCV (4)	2018	DBLP DOI BibTeX RDF
21	Vivek Madan	On approximability and LP formulations for multicut and feedback set problems		2018	RDF
21	Thorsten Beier	Multicut algorithms for neurite segmentation.		2018	RDF
21	Michael Malmros Sørensen	Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes.	Discret. Optim.	2017	DBLP DOI BibTeX RDF
21	Chandra Chekuri, Vivek Madan	Approximating Multicut and the Demand Graph.	SODA	2017	DBLP DOI BibTeX RDF
21	Paul Swoboda, Bjoern Andres	A Message Passing Algorithm for the Minimum Cost Multicut Problem.	CVPR	2017	DBLP DOI BibTeX RDF
21	Siyu Tang 0001, Mykhaylo Andriluka, Bjoern Andres, Bernt Schiele	Multiple People Tracking by Lifted Multicut and Person Re-identification.	CVPR	2017	DBLP DOI BibTeX RDF
21	Alexander Kirillov, Evgeny Levinkov, Bjoern Andres, Bogdan Savchynskyy, Carsten Rother	InstanceCut: From Edges to Instances with MultiCut.	CVPR	2017	DBLP DOI BibTeX RDF
21	Constantin Pape, Thorsten Beier, Peter Li, Viren Jain, Davi D. Bock, Anna Kreshuk	Solving Large Multicut Problems for Connectomics via Domain Decomposition.	ICCV Workshops	2017	DBLP DOI BibTeX RDF