Nathann Cohen
• Member for 11 years, 4 months
• Last seen more than 3 years ago

I'd be surprised if there existed a graph library recognizing them all (there is a lot of them), but most of the algorithms you will find in the litterature are focused on a very small amount of ...

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: http://steinertriples.fr/ If you want to decompose a complete graph ...

If you want to associate to each edge the length of a shortest path between $s$ and $t$, you can begin with computing a shortest path in the whole graph, and associate to each edge not in the shortest ...

According to Bollobas (Random Graphs), if you make "natural assumptions" on $n$ and $m$ there are $n!$ times more labelled graphs on $n$ vertices and $m$ edges than random unlabelled graphs on $n$ ...

You may also like to know that this "sum of squares of the degrees" is also called "First Zagreb Index". When you type it in Google you get results like this one : http://www.springerlink.com/content/...

Give Cliquer a try. http://users.tkk.fi/pat/cliquer.html It's true your graph is huge, but sometimes it works. And it doesn't take long to try it as this software is already (and well) coded :-) ...

If you want to solve actual instances, you will probably like that : http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set Nathann

(This is about the problem in which $|\phi(\Phi^{-1}(i))|\geq 2$ instead of $|\Phi(\phi^{-1}(i))|\geq 2$. Read it too fast. On the bright side Dave fixes it in a comment to this message ) What about ...

There is another way to get a "relaxed version of maximal independent set". Instead of having as constraints "for each edge, the sum is at most 1", the constraints are "for each complete subgraph, the ...

I tried to write a good implementation for precisely this problem, which is now available in Sage. http://www.sagemath.org/doc/reference/sage/graphs/distances_all_pairs.html While Sage is written in ...

I like to think this way too, and I link it with the $P=NP\cap co-NP$ conjecture. It is mentionned there or there (I am having a hard time finding pages about this conjecture as I can only refer to it ...

If you are looking for an implementation, Sage knows how to generate general digraphs up to isomorphism sage: len(list(digraphs(4))) 218 You can then plug in a "test" method if you just want the ...

You main gain significant time by first computing the fractional chromatic index, which would tell quickly if your graph is class 2. Then Vizing's algorithm would probably do. In Sage -- even though ...

There is "Encyclopedia of Algorithms" from 2008, which surveys a lot of different problems (1160 pages of it) http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1

You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess. http://...

Sage doesn't know how to compute treewidth exactly but it can give you the pathwidth of small graphs. http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation....

If you ask questions like that, I feel that the only answers you could get are problems that "reduce to the maximum clique". That would be a mistake. There are many problems in practice where finding ...

I haven't had the occasion to open it yet, but I guess you may be interested in "Exact exponential algorithms" by Fomin and Kratsch (from last year) Here it its table of contents : http://www....

If you want an implementation, Sage has one. With a LP, as usual ;-) http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph....

One of the most amazing theorems in graph theory is Nash-William's : http://en.wikipedia.org/wiki/Strong_orientation .... And its proof is constructive, but not that easy to implement :-)

Sage's implementation of it for instance :-) http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path Nathann

If you are not looking for an algorithm but for an implementation of it and want to solve this problem on an actual graph, this is one of the things Sage (http://sagemath.org/index.html) knows how to ...

I was first going to answer the wrong question : "which example of problems are much harder in hypergraphs than in graphs". I was particularly impressed by the difference in dealing with the maximum ...

One million nodes is far too much for any exact method that I know. This being said, I expect your graph does not have a very large number of edges, so the best is to begin by applying repeatedly this ...

Well, for example did you try sorting the list of outneighrs of each vertex according to their degree ? Sort them once and for all, then each time you do a BFS it will use this ordering, which may be ...

I wanted to post a comment, but with no "karma" it seems impossible... What about using dictionaries (hashmap, depending on the language you use) to store the values of your $f_i$ ? This way you don't ...