3
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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. ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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, ...
0
votes
0answers
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, ...
1
vote
0answers
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} ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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!
-1
votes
1answer
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$ ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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, ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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?
0
votes
0answers
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 ...
7
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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$ ...
3
votes
4answers
471 views

Finding minimal cost edge cover for a bipartie graph

I have got two sets of elements and a pruned graph of bipartie edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
3
votes
1answer
442 views

Simple explanation of Comb inequalities in TSP

A comb can be defined by a handle $H$ and a number of teeths $T_1,T_2,\dots,T_t$ such that: $H,T_1,T_2,\dots,T_t \subseteq V$ $T_j \setminus H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$ $T_j ...
3
votes
1answer
56 views

Convex programming when the problem has an underlying combinatorial structure that's a DAG

I have a nonlinear convex objective function to minimize. The function is defined on a set of variables: $\{ x_1,x_2, \ldots ,x_p \},$ where each $x_i$ is a number associated with a path in the DAG. ...
0
votes
0answers
48 views

An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...
1
vote
0answers
50 views

An optimization involving (random) graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
2
votes
1answer
154 views

Longest cycle containing two nodes

We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle ...
1
vote
0answers
108 views

Shortest path variation

I'm looking for a solution to the following problem, related to shortest path. You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for ...
1
vote
0answers
52 views

“Optimaly” reordering the vertices of a hypergraph.

I am not even sure of how to search for an answer to this, or how to approach the problem myself, so I thought I would try to ask it here. Consider an n-vertex hypergraph where the vertices are ...
4
votes
1answer
203 views

minimum number of vertices for a specific graph

Today I saw this problem: Find the smallest $n\ge 5$ such that there exists a simple graph on $n$ vertices such that any two adjacent vertices have no common neighbours, and any two non-adjacent ...
4
votes
1answer
148 views

Vertex arrangement on the unit sphere

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to ...
4
votes
1answer
205 views

Min Cost Matching for Random Complete Bipartite Graph

Edited I got this problem when reading Goeman's lecture notes http://www-math.mit.edu/~goemans/18433S11/matching-notes.pdf Problem: Exercise 1-16. ...Take a complete bipartite graph with n ...
3
votes
1answer
323 views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...