Comments:

Read the paper, add your comments…

Comments:

Nice coarse-gaining based heuristic to partition the nodes into k sets of similar sizes minimizing the number of edges between those sets. Random maximal matchings are used to coarse-grain the graph. Maybe fast heuristics to obtain a large maximal matching can be considered, such as using the two rules detailed here: [Karp-Sipser based kernels for bipartite graph matching](https://papers-gamma.link/paper/160). Publicly available implementation: http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
Read the paper, add your comments…

Comments:

Read the paper, add your comments…

Comments:

How to efficiently generate combinatorial structures such as posets, trees, B-trees, graphs, permutations, set partitions, Dyck paths, multisets or necklaces ... ? The Ruskey's book gives answers. It contains many surprising descriptions (and bibliographic references) of constant amortized time (CAT) and loopless algorithms.   > **CAT Algorithms** The holy grail of generating combinatorial objects is to find an algorithm that runs in Constant Amortized Time. This means that the amount of computation, after a small amount of preprocessing, is proportional to the number of objects that are listed. We do not count the time to actually output or process the objects; we are only concerned with the amount of data structure change that occurs as the objects are being generated.     _ Ruskey's book, page 8 _   > ** Loopless algorithm ** is an imperative algorithm that generates successive combinatorial objects, such as partitions, permutations, and combinations, in constant time and the first object in linear time     _ https://en.wikipedia.org/wiki/Loopless_algorithm _
Read the paper, add your comments…

Comments:

Nice paper! - Publicly available implementation: https://gitlab.inria.fr/bora-ucar/karp--sipser-reduction - I like Theorem 3.1 a lot! I'm thinking how to generalize it, adapt it, use it for other problems. - Would have liked to see experiments on larger graphs. - Is there any other Rules that could be considered in addition to Rules 1 and 2?
Read the paper, add your comments…
Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33