On Two Segmentation Problems

Noga Alon, Benny Sudakov

Type: Article

Publication Date: 1999-10-01

Citations: 24

DOI: https://doi.org/10.1006/jagm.1999.1024

View Publication

Download PDF

Locations

Journal of Algorithms - View
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	NP-hardness of hypercube 2-segmentation	2014	Uriel Feige
+ PDF Chat	Graph partitioning: an updated survey	2022	Shufei Wu Jianfeng Hou
+	Hypergraph partitions	2019	A. S. Mishchenko Vladimir Manuilov Chao You Han Yang
+	On a tree-partition problem	2007	Peter Katrenič Gabriel Semanišin
+	On Mahler's Partition Problem	1953	W. B. Pennington
+	On Mahler's partition problem	1948	de Ng Dick Bruijn
+	On Partitioning a Graph into Two Connected Subgraphs	2009	Daniël Paulusma Johan M. M. van Rooij
+	Algorithmic and structural aspects of graph partitioning and related problems	2014	Xiaoyan Zhang
+	Randomized greedy algorithms for the hypergraph partitioning problem	1998	Roberto Battiti Alan A. Bertossi Raffaella Rizzi
+ PDF Chat	On the parameterized complexity of Sparsest Cut and Small-Set Expansion problems	2024	Ramin Javadi Amir Nikabadi
+	On several partitioning problems of Bollobás and Scott	2010	Jie Ma Pei-Lan Yen Xingxing Yu
+	On the m-clique free interval subgraphs polytope: polyhedral analysis and applications	2018	Mohammed-Albarra Hassan Imed Kacem Sébastien Martin Izzeldin M. Osman
+	On partitioning a graph into two connected subgraphs	2011	Daniël Paulusma Johan M. M. van Rooij
+	Randomized methods for the number partitioning problem	1996	Michael F. Argüello Thomas A. Feo Olivier Goldschmidt
+	Parameterized Algorithms for Graph Partitioning Problems	2014	Hadas Shachnai Meirav Zehavi
+	Exact and Parameterized Algorithms for the Independent Cutset Problem	2024	J. Rauch Dieter Rautenbach Uéverton S. Souza
+ PDF Chat	Improved Hardness Results of the Cardinality-Based Minimum s-t Cut Problem in Hypergraphs	2024	Florian Adriaens Iiro Kumpulainen Nikolaj Tatti
+	On generalized greedy splitting algorithms for multiway partition problems	2004	Liang Zhao Hiroshi Nagamochi Toshihide Ibaraki
+	On the Zarankiewicz problem for intersection hypergraphs	2016	Nabil H. Mustafa János Pach
+ PDF Chat	On a Covering Problem in the Hypercube	2013	Lale Özkahya Brendon Stanton

Works That Cite This (13)

Action	Title	Year	Authors
+ PDF Chat	Parameterized low-rank binary matrix approximation	2020	Fedor V. Fomin Petr A. Golovach Fahad Panolan
+	A PTAS for $\ell_p$-Low Rank Approximation	2018	Frank Ban Vijay Bhattiprolu Karl Bringmann Pavel Kolev Euiwoong Lee David P. Woodruff
+ PDF Chat	Universal ε-approximators for integrals	2010	Michael Langberg Leonard J. Schulman
+ PDF Chat	Clustering Boolean tensors	2015	Saskia Metzler Pauli Miettinen
+ PDF Chat	On the Complexity of Several Haplotyping Problems	2005	Rudi Cilibrasi Leo van Iersel Steven Kelk John Tromp
+ PDF Chat	Lossy Kernelization of Same-Size Clustering	2022	Sayan Bandyapadhyay Fedor V. Fomin Petr A. Golovach Nidhi Purohit Kirill Siminov
+	Parameterized Low-Rank Binary Matrix Approximation	2018	Fedor V. Fomin Petr A. Golovach Fahad Panolan
+	Approximation Schemes for Low-Rank Binary Matrix Approximation Problems	2018	Fedor V. Fomin Petr A. Golovach Daniel Lokshtanov Fahad Panolan Saket Saurabh
+	A QPTAS for Gapless MEC	2018	Shilpa Garg Tobias Mömke
+ PDF Chat	Approximation Schemes for Low-rank Binary Matrix Approximation Problems	2019	Fedor V. Fomin Petr A. Golovach Daniel Lokshtanov Fahad Panolan Saket Saurabh

Works Cited by This (4)

Action	Title	Year	Authors
+ PDF Chat	Eigenvalues and expanders	1986	Ilan Alon
+	Explicit expanders and the Ramanujan conjectures	1986	Alexander Lubotzky Ralph S. Phillips Peter Sarnak
+ PDF Chat	Approximate counting, uniform generation and rapidly mixing Markov chains	1989	Alistair Sinclair Mark Jerrum
+	A Chernoff Bound for Random Walks on Expander Graphs	1998	David Gillman