CompSci Weekend SuperThread (April 27, 2018) Computer Science

---

• CompSci Weekend SuperThread (April 27, 2018)
• Checking graph isomorphisms - I need some misconceptions cleared
• Does anyone happen to have a matlab implementation of an algorithm to compute girth of a graph?
• Why Do Neural Networks Need An Activation Function? (by Computer Vision Specialist)
• How to deploy Laravel to Kubernetes

CompSci Weekend SuperThread (April 27, 2018) Posted: 26 Apr 2018 06:06 PM PDT /r/compsci strives to be the best online community for computer scientists. We moderate posts to keep things on topic. This Weekend SuperThread provides a discussion area for posts that might be off-topic normally. Anything Goes: post your questions, ideas, requests for help, musings, or whatever comes to mind as comments in this thread. Pointers If you're looking to answer questions, sort by new comments. If you're looking for answers, sort by top comment. Upvote a question you've answered for visibility. Downvoting is discouraged. Save it for discourteous content only. Caveats It's not truly "Anything Goes". Please follow Reddiquette and use common sense. Homework help questions are discouraged. submitted by /u/AutoModerator [link] [comments]

Checking graph isomorphisms - I need some misconceptions cleared Posted: 27 Apr 2018 04:05 AM PDT Hey guys, I'm reading through The Algorithm Design Manual by Skiena and I have a misunderstanding about checking for graph isomorphism. Definition of a graph isomorphism is (by the book, page 550): Find a (or all) mapping f from the vertices of G to the vertices of H such that G and H are identical; i.e. , (x, y) is an edge of G iff (f(x), f(y)) is an edge of H. However, when the author explains how to proceed with constructing the algorithm of finding the isomorphism, he says: Although no worst-case polynomial-time algorithm is known, testing isomorphism is usually not very hard in practice. The basic algorithm backtracks through all n! possible relabelings of the vertices of graph h with the names of vertices of graph g, and then tests whether the graphs are identical. Of course, we can prune the search of all permutations with a given prefix as soon as we detect any mismatch between edges whose vertices are both in the prefix. The thing that bothers me is this: all n! possible relabelings of the vertices of graph h with the names of vertices of graph g Why do we relabel the vertices? Aren't vertex names arbitrary? Shouldn't we exchange edge weights instead of vertex names (labels)? This doesn't hold for when the graph is unweighted. If the graph is unweighted, then I wouldn't exchange the edge weights, but rather go through all vertices of one graph (one by one) and check if there is a vertex with a matching number of edges in the second graph. If there is, I would "cross it off" (maybe by setting some bool array element equaling the index of that node equal to false) and then I'd proceed. No relabeling needed. Time complexity O(n2). Let me know what you think. submitted by /u/The_Grey_Wolf [link] [comments]

Does anyone happen to have a matlab implementation of an algorithm to compute girth of a graph? Posted: 26 Apr 2018 10:55 PM PDT Title says it all. Don't wanna waste time writing it if one of you had it on hand. Didn't see anything obvious on Google, but my google-fu may be failing me. Ideally, this would take as input an adjacency matrix. submitted by /u/the_Rag1 [link] [comments]

Why Do Neural Networks Need An Activation Function? (by Computer Vision Specialist) Posted: 26 Apr 2018 08:49 PM PDT submitted by /u/Batareika_1 [link] [comments]

How to deploy Laravel to Kubernetes Posted: 26 Apr 2018 07:38 PM PDT submitted by /u/keithmifsud [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States