# Tagged Questions

17 views

### Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e$, where $a_e>0$. For a fixed $t$ we can define ...
30 views

### Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
19 views

### Steiner tree problem in 3D?

Steiner tree problem in the plane (2D) is explained on wiki that though there's no straight solution, the solution has some properties, namely points added to the graph (Steiner points) must have a ...
30 views

### connectivity on graph

Given a graph, undirected or directed, what is the optimal or just good algorithm for finding the following? 1) Whether two vertices are connected. 2) The shortest path going from one to the other. ...
42 views

### Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
37 views

### Keller 6 graph and maximum clique

Based on the DIMACS maximum clique benchmark, http://iridia.ulb.ac.be/~fmascia/maximum_clique/, the Keller 6 graph contains a clique of size 59. The clique number however is at least 59 (as can be ...
29 views

### Finding coordinates of nodes in a graph

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other ...
43 views

### How many triangles may a connected simple graph with m edges have at most?

Suppose a connected simple graph has m edges and there are at most n vertices and the degree of each vertex is at least ...
17 views

### Generalization of size reduction of Linear Assignment Problems

It is well known, that the LAP has super linear complexity. Hence, problem-size reduction is a viable optimization strategy. For instance, if one task is incident to exactly two workers, one can ...
38 views

### Constrained Minimization Problem derived from a Directed Graph

I'm looking for a solution the following graph problem for data analysis purposes. Basically, I have a directed graph of $N$ nodes where I know the following: The sum of the weights of the ...
299 views

### Finding the max flow of an undirected graph with Ford-Fulkerson

Given the following undirected graph, how would I find the max-flow/min-cut? Now, I know that in order to solve this, I need to redraw the graph so that it is directed as shown below. However, ...
28 views

### Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
74 views

### Proving a minimum spanning tree is unique iff any edge (a,b) not in T has larger weight than any edge on the circuit created by adding it

Proving a minimum spanning tree is unique iff any edge (a,b) not in T has larger weight than any edge on the circuit created by adding it I'm not sure how to prove this because I'm new to these style ...
54 views

### minimum strength of the edges occurring in any path P

Let $G=(V,E)$ be a graph and let $s: E \to \mathbb{R}^+$ be a function. Let us call $s(e)$ the strength of the edge $e$. For any path $P$ in $G$, the reliability of $P$ is, by definition, the minimum ...
122 views

### Area optimization: Packing rectangles inside rectangle

Background: I am scrambling to figure out the optimization algorithm to build sprite image, which is essentially a big container rectangular image, with multiple rectangular images. I have found an ...
36 views

### Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ...
59 views

### travelling salesman problem with pairs of cities and constraints

I am looking for the name of the following two problems, and an approach to solve them. Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, ...
29 views

### Maximization problem on a graph

Consider a graph $G(V,E)$. Let degree of each vertex be denoted to $\beta(v) < d$. Maximize the following, where $\beta(v)$ is the only variable for all vertex $v\in V$.  \max \sum_{(u,v)\in E} ...
97 views

### Prison break: a minimisation problem

Consider a prison with $n$ prisoners. Each cell contains a phone which can be used to call any other cell. Each prisoner has a different piece of information which, when put together, will ...
62 views

### Combinatorics : Prove - Graph Algorithm

I am studying Graph Algorithms. I can solve the graph algorithm problems but I am confused with this proposition. If I were to prove this proposition, how would I start? Can anyone help here? Thank ...
55 views

### computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
82 views

### Lp optimal solution question

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
101 views

### Crystal structure, lattice, periodic graph and coloring

I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field. Given a periodic graph (actually a physical ...
106 views

### Sort objects into groups based on group size preference

I have a research question that involves human subjects being sorted into groups before playing a social game. Before sorting, each person decides on their preferred group size, from 1 to n; where n ...
72 views

### Mathematical formulation for maximum sum of edge weights

For my academic research purposes, I have a situation as below. The initial problem looks as in below figure. I need to find one match for each of P1,P2,P3 from the right side such that the sum of ...
119 views

### Multivariable calculus: optimizing for shortest path along a curvy plane?

I want to write a computer program which can help me spend the least amount of energy and time walking between locations on my university campus. My campus is very hilly, and it is also extremely hot ...
33 views

### Highest known minimum bipartite crossing number?

I'd like to know what the highest known complete bipartite minimum crossing number graph K is? Last I knew it was K 7,7 , has K 8,8 been conjectured or proven yet? Any info on where I could find ...
40 views

### Split graph into groups of edges that are not adjacent

I need to split graph, another say to color it into some groups of unadjacent edges. Minimize number of groups is not the only goal to achive. Group of every size has its's own weight, e.g. 64 - 1, ...
62 views

### Linear constraints on distance (hop) matrix of a tree

I have an optimization problem where I want the constraints to be linear. The variables are elements of an $N\times N$ matrix D. The elements of D, ie $D(i,j)$ are integers and represent the number of ...
65 views

### Subset of graph with minimum nodes minimum edges pointing out of the subset

Given a Directed Graph $G$ and a node $n$ in that graph I'd like to find a subgraph $S$ of $G$ with the following conditions: $n \in S$ $a *$ number of nodes in $S$ + $b *$ number of edges going ...
48 views

### What is that type of TSP

I'm searching for the name of the TSP-like problem. The basic principal is like it follows: When a city is visited by the salesman, he will came in one point and exit the city in another. The ...
136 views

### Finding the fractional vertex-cover number ($\tau ^ \star$) for k-cycle hypergraphs.

Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$. A quite ...
73 views

### How to effectively detect negative cycles in graph?

I proposed to check the edge weighs and then run shortest path and check if the shortest path weight is not going to $-\infty$. Any better ideas?
177 views

### Using maximum flow algorithm to check existence of a matrix

Using the maximum flow algorithm, I have to determine if there exists a $3\times 3$ matrix $P$ (such that all elements are $\geq 0$). I'm given: The maximum values of the row sums The column sums ...
351 views

### Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
59 views

### Optimal distribution of weighted votes

I'm working on a project for my university in wich the students can choose their preferred seminars for the next semester. My goal is it to allocate these weighted votes in an optimal way to the ...
186 views

### Max-weight path of fixed length?

I have a problem which I've reduced down to the following requirements: Given an: undirected graph $G$ that may contain cycles, with positive weighted nodes and edges of length $1$, a subset of ...
123 views

### Properties of shortest walks and simple paths during optimization

Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ ...