# All Questions

11 questions
Filter by
Sorted by
Tagged with
625 views

### Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
857 views

### Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
183 views

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ... 2answers 2k views ### Real world applications for Steiner Tree Problem? Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ... 1answer 365 views ### Relationship between graph expansion and conductance I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is: Could someone point me to a reference that discusses both of these notions? ... 1answer 88 views ### Chazelle's discrepancy book: greedy method In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem ... 1answer 885 views ### Asymptotics of the number of words in a regular language of given length For a regular language$L$, let$c_n(L)$be the number of words in$L$of length$n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for$L$), one can show that ... 3answers 249 views ### How many Turing Machines are there that run in time$t$or in space$s$on inputs of length$k\$?

I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question. My ...
926 views

### Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...