From 90dc84116ad6aba3dcc3f53b163c4b4cb9586e1d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 30 Aug 2008 14:00:16 +0200 Subject: [PATCH] Written a new TODO list. --- PLAN | 65 ------------------------------------------------------------ TODO | 16 +++++++++++++++ 2 files changed, 16 insertions(+), 65 deletions(-) delete mode 100644 PLAN create mode 100644 TODO diff --git a/PLAN b/PLAN deleted file mode 100644 index 51732fb..0000000 --- a/PLAN +++ /dev/null @@ -1,65 +0,0 @@ -* Minimum Spanning Trees - - o The Problem - o Basic properties - o Red/Blue meta-algorithm - o Classical algorithms - o Contractive algorithms - -* Fine Details of Computation - - o Models and machines - o Radix-sorting - o Bit tricks - o Q-Heaps - -* Advanced MST Algorithms - - o Minor-closed classes - o Fredman-Tarjan algorithm - o MST verification - o Linear-time verification - o A randomized algorithm - o Special cases and related problems - -* Approaching Optimality - - o Soft heaps - o Robust contractions - o Decision trees - o An optimal algorithm - -* Dynamic MST algorithms - - o (Semi-)dynamic algorithms - o ET-trees - o Fully dynamic connectivity - o Dynamic MST - o Almost minimum trees - -* Ranking Combinatorial Objects - - o Ranking and unranking - o Ranking of permutations - o Ranking of k-permutations - o Restricted permutations - o Hatcheck lady and other derangements - -TODO: - -Applications: - -- degree-restricted cases and arborescences -- bounded expansion classes? - -Ranking: - -- ranking of permutations on general sets, relationship with integer sorting -- JN: 4.5.1: neslo by preci isolovat nejaky vlstnosti restriction matrices - tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat) - co je to vlastne za matice co splnuji 4.5.2 -- JN: bounded-degree restriction graphs; would it imply general speedup? - -Typography: - -- formatting of multi-line \algin, \algout diff --git a/TODO b/TODO new file mode 100644 index 0000000..24a6438 --- /dev/null +++ b/TODO @@ -0,0 +1,16 @@ +Applications: + +- degree-restricted cases and arborescences +- bounded expansion classes? + +Ranking: + +- ranking of permutations on general sets, relationship with integer sorting +- JN: 4.5.1: neslo by preci isolovat nejaky vlstnosti restriction matrices + tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat) + co je to vlastne za matice co splnuji 4.5.2 +- JN: bounded-degree restriction graphs; would it imply general speedup? + +Typography: + +- formatting of multi-line \algin, \algout -- 2.39.2