학술논문
Open Problems in (Hyper)Graph Decomposition
Document Type
Working Paper
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; Yzelman, Albert-Jan
Source
Subject
Language
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.