Search

Your search keyword '"Uçar, Bora"' showing total 11 results
Start Over Author "Uçar, Bora" Publication Year Range Last 3 years
11 results on '"Uçar, Bora"'

1. Open Problems in (Hyper)Graph Decomposition

Author

Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Karypis, George, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Schulz, Christian, Sharma, Roohani, Strash, Darren, Sullivan, Blair D., Uçar, Bora, and Yzelman, Albert-Jan

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.

Published
2023

3. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Author

George Karypis and Christian Schulz and Darren Strash and Deepak Ajwani and Rob H. Bisseling and Katrin Casel and Ümit V. Çatalyürek and Cédric Chevalier and Florian Chudigiewitsch and Marcelo Fonseca Faraj and Michael Fellows and Lars Gottesbüren and Tobias Heuer and Kamer Kaya and Jakub Lacki and Johannes Langguth and Xiaoye Sherry Li and Ruben Mayer and Johannes Meintrup and Yosuke Mizutani and François Pellegrini and Fabrizio Petrini and Frances Rosamond and Ilya Safro and Sebastian Schlag and Roohani Sharma and Blair D. Sullivan and Bora Uçar and Albert-Jan Yzelman, Karypis, George, Schulz, Christian, Strash, Darren, Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Sharma, Roohani, Sullivan, Blair D., Uçar, Bora, Yzelman, Albert-Jan, George Karypis and Christian Schulz and Darren Strash and Deepak Ajwani and Rob H. Bisseling and Katrin Casel and Ümit V. Çatalyürek and Cédric Chevalier and Florian Chudigiewitsch and Marcelo Fonseca Faraj and Michael Fellows and Lars Gottesbüren and Tobias Heuer and Kamer Kaya and Jakub Lacki and Johannes Langguth and Xiaoye Sherry Li and Ruben Mayer and Johannes Meintrup and Yosuke Mizutani and François Pellegrini and Fabrizio Petrini and Frances Rosamond and Ilya Safro and Sebastian Schlag and Roohani Sharma and Blair D. Sullivan and Bora Uçar and Albert-Jan Yzelman, Karypis, George, Schulz, Christian, Strash, Darren, Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Sharma, Roohani, Sullivan, Blair D., Uçar, Bora, and Yzelman, Albert-Jan

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.

Published
2024
Full Text
View/download PDF

4. Engineering fast algorithms for the bottleneck matching problem

Author

Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, Uçar, Bora, Neo4j, Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)

Subjects
bipartite graphs, matching, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], assignment problem
Abstract

International audience; We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to determine a maximum cardinality matching in which the minimum weight of an edge is the maximum. To the best of our knowledge, there are two widely used solvers for this problem based on two different approaches. There exists a third known approach in the literature, which seems inferior to those two which is presumably why there is no implementation of it. We take this third approach, make theoretical observations to improve its behavior, and implement the improved method. Experiments with the existing two solvers show that their run time can be too high to be useful in many interesting cases. Furthermore, their performance is not predictable, and slight perturbations of the input graph lead to considerable changes in the run time. On the other hand, the proposed solver's performance is much more stable; it is almost always faster than or comparable to the two existing solvers, and its run time always remains low.

Published
2023

5. Engineering Fast Algorithms for the Bottleneck Matching Problem

Author

Ioannis Panagiotas and Grégoire Pichon and Somesh Singh and Bora Uçar, Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, Uçar, Bora, Ioannis Panagiotas and Grégoire Pichon and Somesh Singh and Bora Uçar, Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, and Uçar, Bora

Abstract

We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to find a maximum cardinality matching in which the minimum weight of an edge is the maximum. To the best of our knowledge, there are two widely used solvers for this problem based on two different approaches. There exists a third known approach in the literature, which seems inferior to those two which is presumably why there is no implementation of it. We take this third approach, make theoretical observations to improve its behavior, and implement the improved method. Experiments with the existing two solvers show that their run time can be too high to be useful in many interesting cases. Furthermore, their performance is not predictable, and slight perturbations of the input graph lead to considerable changes in the run time. On the other hand, the proposed solver’s performance is much more stable; it is almost always faster than or comparable to the two existing solvers, and its run time always remains low.

Published
2023
Full Text
View/download PDF

9. A Branch-And-Bound Algorithm for Cluster Editing

Author

Bläsius, Thomas, Fischbeck, Philipp, Gottesbüren, Lars, Hamann, Michael, Heuer, Tobias, Spinner, Jonas, Weyand, Christopher, Wilhelm, Marcus, Schulz, Christian, and Uçar, Bora

Subjects
editing, cluster editing, Mathematics of computing → Graph algorithms, DATA processing & computer science, ddc:004, cluster
Abstract

The cluster editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge., LIPIcs, Vol. 233, 20th International Symposium on Experimental Algorithms (SEA 2022), pages 13:1-13:19

Published
2022
Full Text
View/download PDF

10. LIPIcs, Volume 233, SEA 2022, Complete Volume

Author

Schulz, Christian and Uçar, Bora

Subjects
Data processing Computer science, Theory of computation → Design and analysis of algorithms, ddc:004, LIPIcs, Volume 233, SEA 2022, Complete Volume
Abstract

LIPIcs, Volume 233, SEA 2022, Complete Volume, LIPIcs, Vol. 233, 20th International Symposium on Experimental Algorithms (SEA 2022), pages 1-434

Published
2022

11. Front Matter, Table of Contents, Preface, Conference Organization

Author

Schulz, Christian and Uçar, Bora

Subjects
Conference Organization, Table of Contents, Theory of computation → Design and analysis of algorithms, Preface, Front Matter
Abstract

Front Matter, Table of Contents, Preface, Conference Organization, LIPIcs, Vol. 233, 20th International Symposium on Experimental Algorithms (SEA 2022), pages 0:i-0:xii

Published
2022
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results