Creating a directed weighted graph by using a database

Given a database in matrix format:

SeedRandom[6]; mat = RandomInteger[5, {27, 30}]; mat[[1, All]] = {"", a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2,     c3, c4, c5, d1, d2, d3, d4, d5, afd1, afd2, bfd1, bfd2, cfd1, cfd2,    dfd1, dfd2, TD}; mat[[All, 1]] = {"", a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2,     c3, c4, c5, d1, d2, d3, d4, d5, aT, bT, cT, dT, VA, TS}; 

Each row and column has a name, e.g., a1, a2, .... Suppose the following operations on mat.

  1. Drop the columns {a1, a3, b1, b2, c4, c5, d2, d5} and the rows with the same names.
  2. Create a weighted directed graph using the columns {a2, a4, a5, b3, b4, b5, c1, c2, c3, d1, d3, d4} and the rows with the same names.

My question is not about the operations referred to in [1] and [2]. I like to know how to keep the linkage between a string vertex name and a numeric vertex name. String names for the list in [2] are {a2, a4, a5, b3, b4, b5, c1, c2, c3, d1, d3, d4} and the associated numeric names are {2, 4, 5, 8, 9, 10, 11, 12, 13, 16, 18, 19}.

Because my original matrix is large, with the operation in item [1], I lose the linkage between numeric and string names, which I need in later stages of output formatting. For example, I can easily find Cliques with numeric vertex names but I need to know the string names linked to the numeric vertices.

Any suggestion?

Schedule Optimization With Priority and Weighted Costs

I need an algorithm to determine the best itinerary for a series of events.

Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each event is at a physical location thus it takes time to travel from event to event. It is not necessary to attend every event.

What itinerary will yield the largest total reward?

Does anyone know if there is an existing algorithm for this or one that would be easily adapted? Given the similarity to the traveling salesman problem I am tempted to start with a weighted TSP solution and work from there.

Combinatorial Problem similar in nature to a special version of max weighted matching problem

I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.

I have a general graph $ G(\mathcal{V},\mathcal{E},\mathcal{W})$ . I want to find a maximum weight matching of the graph $ G$ that must cover a certain subset of vertices and has a specific size. For example, if I have a graph with eight vertices, I want to find a max weighted matching that must cover the subset of vertices $ \mathcal{V}’=\{1,2,3\}$ and the size of the matching is $ \lceil{|\mathcal{V}’|/2}\rceil$ . So one more vertex needs to be chosen that maximizes the weighted matching. How to find the optimal solution in polynomial time if possible?

Minimum Weighted Vertex Cover, Dynamic Programming


So my solution in my mind right now:

Let $ OPT(n, boolean)$ be the minimum vertex cover rooted at vertex n that includes that vertex if boolean is true, false otherwise.

So my idea is:

If a vertex is not included, any edges leading away from it, their vertices are to be part of the vertex cover. $ OPT(n, F) = OPT(n.left, T) + OPT(n.right, T)$

If a vertex is included, it can or can not be included, the vertex at the other end of an edge. $ OPT(n, T) = min\{OPT(n.left, T) + OPT(n.right, T), OPT(n.left, F) + OPT(n.right, F), OPT(n.left, F) + OPT(n.right, T), OPT(n.left, T) + OPT(n.right, F)\} + n.weight $

Then we can solve this problem with $ min\{OPT(root, T), OPT(root, F)\}$

Is this the right idea? Is there anything I might be missing? If so, what would be the correct approach?

How to minimize diffusion in undirected weighted graph

I’ve got a work that has to do with networks, where each edge has a weight ($ w\in(0,1)$ ) and some random set of nodes are ‘infected’. I don’t know which nodes are (or how many). The diffusion spread is according to linear threshold model (with some random threshold $ \theta\in(0.3,0.5)$ . I’m allowed to delete only $ 10\%$ of edges from the original graph, before the parameters are set (I don’t know the initial infected nodes, nor the threshold a-priori).

I’ve tried multiple methods like:

  1. removing highest weighted edges first – that results good performance when only small amount of initial infected nodes is given.
  2. removing local-bridges – I’ve sorted the edges by neighbourhood overlap, and then removed by weight. – This works good for low thresholds.
  3. Multiple variations of vertex cover, edge cover, centrality, betweenness etc – all underperformed the “naive” remove by weight approach (presented in (1)).
  4. Clustering heuristics – tried to construct clusters and remove cutting edges (by weight, etc).

I find it hard to “accept” that approach (1) which seem to be very naive – outperforms all other.

Also, went over several papers and implemented some of the suggested ideas – none outperformed that naive approach.

I will appreciate if anyone with similar experience has anything to suggest.

Shortest path using less than or equal to m edges in a directed, weighted graph with negative cycles

I’m solving a problem:

Given a directed, weighted graph $ G$ that has $ V$ vertices and $ E$ edges and a positive integer $ m$ , describe an algorithm that finds the length of the shortest path using less than or equal to $ m$ edges. Note that the graph may contain negative cycles.

First, I tried Bellman-Ford algorithm, but I cannot deal with negative cycles. Next, I tried one using recursive DFS, but it takes too much time! I think dynamic programming may solve this problem, but I don’t know how to start with DP. Is there any fancy way to solve this problem in short time?

Heuristic algorithm for the minimum weighted s-t cut with linear running time

To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $ O(n^{2}\sqrt{m})$ time complexity. I’m interested in solving this problem as a separation sub-problem inside a branch and cut algorithm, so I don’t always need the optimal solution. Is there a heuristic/approximation/randomized algorithm for the min s-t cut problem with better time complexity?