Reputation
24,639
Top tag
Next privilege 25,000 Rep.
Access to site analytics
Badges
5 20 68
Newest
 Good Answer
Impact
~532k people reached

3h
awarded  Good Answer
Apr
28
comment Is there an efficient algorithm to find all the maximum matching in any tree?
@DanielAlejandroJaume If you want all the edges that belong to some maximum matching, that should be much easier.
Apr
27
comment Is there an efficient algorithm to find all the maximum matching in any tree?
@DanielAlejandroJaume Simplex works well in most cases for different reasons, it's exponential only for very special cases. On the other hand, in this problem I would guess that then number of matchings of a random tree on $n$ vertices is exponential in the number of leaves it has.
Apr
26
comment Is there an efficient algorithm to find all the maximum matching in any tree?
@DanielAlejandroJaume But if there are too many, then no efficient algorithm could list them all (normally you measure complexity with regard to input, not output).
Apr
26
answered Is there an efficient algorithm to find all the maximum matching in any tree?
Apr
26
revised How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$?
added 68 characters in body
Apr
26
revised How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$?
added 68 characters in body
Apr
26
revised How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$?
added 518 characters in body
Apr
26
answered How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$?
Apr
15
answered Is it possible to find Hamilton path in this graph?
Apr
13
comment Show that $f(n) \in \Theta(n^k)$
Welcome to math.SE! Could you provide any context for this problem (e.g., what topics did you cover, where the question comes from, what course you are attending, etc.)? Also, what have you tried?
Apr
13
comment Why polynomial functions f(x)+g(x) = (f+g)(x)?
If you have trouble understanding this, consider $(f+g)$ as a name, e.g. you could define $h(x) = f(x) + g(x)$, only that you use symbol $(f+g)$ instead of $h$. The upside of this is that you need a new definition for any new name like $h$, but it is obvious what $(f+f)$ means or $(g+h)$ or even $(f + (f + g))$.
Apr
13
awarded  Populist
Apr
8
comment Infinite graph theory: What's a tree?
@user21820 I think we disagree on something else entirely, and if that is true then I misunderstood your comment. Frequently we impose some additional structure on an object to make it easier to handle (like a root in a tree). However, unless that structure was there in the first place (i.e. it was intrinsic to that object), I would not say that this object has/had this structure. For example, if I direct edges of a graph, I say I create a new graph. Assuming that the imposed structure becomes the property of an object, I clearly agree with you.
Apr
7
revised A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching
added 762 characters in body
Apr
7
comment A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching
@ArmanMalekzade I could not know that, because you provided no context to the question. I would advise you to add it, otherwise the people that could answer your question have very limited knowledge of what would actually help you. Context is very important, consider this when asking your future questions!
Apr
7
comment Infinite graph theory: What's a tree?
@user21820 I disagree with the sentiment that in computer science trees are (almost) always directed. That is true if the tree in question is rooted (which indeed is often the case). However, trees described by the OP are unrooted, and these also happen frequently in computer science and they do not come with any default way of directing the edges (unless, of course, the underlying graph was directed in the first place).
Apr
7
answered A bipartite graph with a perfect matching has a vertex with each edge contained in a perfect matching
Apr
5
answered Show that if G is a connected simple k-regular graph with k ≥ 2 and χ'(G) = k, then G is Hamiltonian
Apr
5
comment Show that if G is a connected simple k-regular graph with k ≥ 2 and χ'(G) = k, then G is Hamiltonian
@Math1000 That's not true, just consider a cube with each direction X,Y,Z colored different way. You have to use all the three colors to get the Hamilton cycle.