Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Antares Chen, Lorenzo Orecchia, and Erasmo Tani. Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{chen_et_al:LIPIcs.ICALP.2025.49,
author = {Chen, Antares and Orecchia, Lorenzo and Tani, Erasmo},
title = {{Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game}},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
pages = {49:1--49:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-372-0},
ISSN = {1868-8969},
year = {2025},
volume = {334},
editor = {Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.49},
URN = {urn:nbn:de:0030-drops-234261},
doi = {10.4230/LIPIcs.ICALP.2025.49},
annote = {Keywords: Hypergraph Partitioning, Cut Improvement, Cut-Matching Game}
}
Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Karthekeyan Chandrasekaran, Chandra Chekuri, and Shubhang Kulkarni. On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{chandrasekaran_et_al:LIPIcs.ICALP.2025.43,
author = {Chandrasekaran, Karthekeyan and Chekuri, Chandra and Kulkarni, Shubhang},
title = {{On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions}},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
pages = {43:1--43:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-372-0},
ISSN = {1868-8969},
year = {2025},
volume = {334},
editor = {Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.43},
URN = {urn:nbn:de:0030-drops-234200},
doi = {10.4230/LIPIcs.ICALP.2025.43},
annote = {Keywords: Combinatorial Optimization, Approximation Algorithms, Randomized Algorithms, Hardness of Approximation, Densest Subgraph, Supermodular Functions, Submodular Set Cover}
}
Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Nairen Cao, Shi Li, and Jia Ye. Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{cao_et_al:LIPIcs.ICALP.2025.40,
author = {Cao, Nairen and Li, Shi and Ye, Jia},
title = {{Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering}},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
pages = {40:1--40:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-372-0},
ISSN = {1868-8969},
year = {2025},
volume = {334},
editor = {Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.40},
URN = {urn:nbn:de:0030-drops-234171},
doi = {10.4230/LIPIcs.ICALP.2025.40},
annote = {Keywords: Correlation Clustering, All-Norms, Approximation Algorithm, Massively Parallel Algorithm}
}
Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Nick Fischer, Evangelos Kipouridis, Jonas Klausen, and Mikkel Thorup. A Faster Algorithm for Constrained Correlation Clustering. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{fischer_et_al:LIPIcs.STACS.2025.32,
author = {Fischer, Nick and Kipouridis, Evangelos and Klausen, Jonas and Thorup, Mikkel},
title = {{A Faster Algorithm for Constrained Correlation Clustering}},
booktitle = {42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
pages = {32:1--32:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-365-2},
ISSN = {1868-8969},
year = {2025},
volume = {327},
editor = {Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.32},
URN = {urn:nbn:de:0030-drops-228585},
doi = {10.4230/LIPIcs.STACS.2025.32},
annote = {Keywords: Clustering, Constrained Correlation Clustering, Approximation}
}
Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Manuel Lafond, Alitzel López Sánchez, and Weidong Luo. Cluster Editing on Cographs and Related Classes. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 64:1-64:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{lafond_et_al:LIPIcs.STACS.2025.64,
author = {Lafond, Manuel and L\'{o}pez S\'{a}nchez, Alitzel and Luo, Weidong},
title = {{Cluster Editing on Cographs and Related Classes}},
booktitle = {42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
pages = {64:1--64:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-365-2},
ISSN = {1868-8969},
year = {2025},
volume = {327},
editor = {Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.64},
URN = {urn:nbn:de:0030-drops-228895},
doi = {10.4230/LIPIcs.STACS.2025.64},
annote = {Keywords: Cluster editing, cographs, parameterized algorithms, clique-width, trivially perfect graphs}
}
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Junhao Gan, David F. Gleich, Nate Veldt, Anthony Wirth, and Xin Zhang. Graph Clustering in All Parameter Regimes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gan_et_al:LIPIcs.MFCS.2020.39,
author = {Gan, Junhao and Gleich, David F. and Veldt, Nate and Wirth, Anthony and Zhang, Xin},
title = {{Graph Clustering in All Parameter Regimes}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {39:1--39:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Esparza, Javier and Kr\'{a}l', Daniel},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.39},
URN = {urn:nbn:de:0030-drops-127065},
doi = {10.4230/LIPIcs.MFCS.2020.39},
annote = {Keywords: Graph Clustering, Algorithms, Parametric Linear Programming}
}
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
David F. Gleich, Nate Veldt, and Anthony Wirth. Correlation Clustering Generalized. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gleich_et_al:LIPIcs.ISAAC.2018.44,
author = {Gleich, David F. and Veldt, Nate and Wirth, Anthony},
title = {{Correlation Clustering Generalized}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {44:1--44:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.44},
URN = {urn:nbn:de:0030-drops-99925},
doi = {10.4230/LIPIcs.ISAAC.2018.44},
annote = {Keywords: Correlation Clustering, Approximation Algorithms}
}