Skip to main content

Questions tagged [graphs]

For questions related to graphs, a mathematical object consisting of a set of nodes with edges connecting certain pairs of them.

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers

Multiple shipments with FILO order

I am trying to solve a problem statement with the help of jsprit. There is a depot. Identical items need to be delivered or picked up. An item can have two states: Bad or good. Bad items need to be ...
Aman Kumar's user avatar
7 votes
0 answers

MIP formulation for graph planarity test

In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that ...
Kuifje's user avatar
  • 13.5k
6 votes
0 answers

Graph coloring problem while counting cliques

Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$. Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$. For a set of nodes $X\subset V$, we denote $f(X)$ ...
Jin Kazama's user avatar
5 votes
0 answers

Reduction from Steiner Tree to TSP

The Steiner Tree version that I am considering is the following: given an undirected weighted graph $G=(V,E)$ and a subset of vertices $T \subseteq V$, find a minimum tree that connects all the ...
user12632521's user avatar
4 votes
0 answers

Simplified risk game: writing a pratical Minimax objective for mixed integer programming

Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
Qurious Cube's user avatar
3 votes
0 answers

Flow problem with flow demands

Recently I found a subproblem in a project I am working with. This problem is a sort of flow variant, as you will see. And I am looking for literature-related articles and also fast approaches for ...
Matheus Diógenes Andrade's user avatar
3 votes
0 answers

Looking for Balas' original JSP-as-digraph paper

I'm looking for E. Balas' original paper "Finding a Minimaximal Path in a Disjunctive PERT Network". Is this paper available via the web? Google and my campus library are unable to help me ...
Brannon's user avatar
  • 900
3 votes
0 answers

What can traditional graph cut methods do well, that deep learning cannot?

I have been fascinated by the rise and fall of graph cut algorithms in recent years, which I described in this question: Was there something specific that caused graph cuts to lose popularity in the ...
Nike Dattani's user avatar
  • 1,278
3 votes
0 answers

Graph matching with apriori information about the matches?

Given two graphs with n vertices each, where apriori information regarding the similarity of each pair of vertices (between the source and target nodes) is given, is there a known concept for finding ...
DsCpp's user avatar
  • 131
3 votes
0 answers

Power grid distribution and recipient bias

I have a strong feeling that this problem I'm trying to solve has already been done by someone much smarter than me at one point and I'm more looking at where I can research a topic further rather ...
Craig's user avatar
  • 31
3 votes
0 answers

Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?

I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
WindBreeze's user avatar
2 votes
2 answers

Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
Changxin Cao's user avatar
2 votes
0 answers

Multi-objective optimization with known variable dependencies (via a graph) -- what is this called?

Suppose that I am trying to solve a standard multi-objective optimization problem: $$ \min_{ \begin{array}{c} \textbf{x} \in S \end{array} } \left [ f_1(\textbf{x}),f_2(\...
Astrid's user avatar
  • 121
2 votes
0 answers

Order picking optimization: creating links between sectors of the warehouse

In the Conference Paper A Generic Approach for Order Picking Optimization Process in Different Warehouse Layouts, I cannot understand the process described on page 4: That is done by creating new ...
GuglielmoSanchini's user avatar
2 votes
0 answers

Are the operations in the Graph Edit Distance problem of interest?

In the graph edit distance (GED), we are looking to find the cost of modifying one graph $G_1$ to another graph $G_2$. Is the sequence of operations that take $G_1$ from $G_2$ of interest in this ...
David's user avatar
  • 333
2 votes
0 answers

Node ordering in Graph optimization

I'm solving a network optimization problem which is modeled as a graph $G=(V,E)$. Solving this problem using Pulp and NetworkX in Python and ordering the graph's nodes in a certain order (i.e. (1,2,3,...
Amedeo's user avatar
  • 443
2 votes
0 answers

Is this a common generalization of the independent set problem?

Suppose a minimum weighted independent set in a conflict graph with $n$ vertices. The basic version is where each vertex $i$ is associated with a weight $c_i$. i.e., there is a vector $C$ for the ...
Mostafa's user avatar
  • 2,104
2 votes
0 answers

Simplex - Network flow problem : Arc from 1 to P with infinite capacity

The Network - Maximum flow problem below aims to find the maximum flow using simplex method : With the LP as follow : LP : \begin{Bmatrix} Z(Max) = \sum_{i=1}^{m} fi \\ Af =0 \end{Bmatrix} ...
JirenOppaik's user avatar
1 vote
0 answers

Complexity of cardinality constrained maximum weight independent set problem

Given a graph with a set of nodes and edges, the goal of the maximum independent set problem is to find the maximum number of vertices where no two vertices are adjacent. This is well-known NP-hard ...
Mostafa's user avatar
  • 2,104
1 vote
0 answers

Need help with a model to optimize a trail in directed graph

The graph in the image represents the production sequencing on a machine with production capacity C in volume. Each node N represents a different product with a profit L per volume produced. Every ...
Maria's user avatar
  • 11
1 vote
0 answers

Bipartite matching

If I have two matrix $$A = \begin{bmatrix} 1 & 2 \\ 2 & 3 \end{bmatrix} $$ and $$B = \begin{bmatrix} 3 & 4 \\ 5 & 3 \end{bmatrix} $$ We have to make a matching between $A$ and $B$ ...
Ishaan's user avatar
  • 139
0 votes
0 answers

Spectral clustering with laplacian matrix eigenvector

I want to separate a given graph in $k$ clusters with the laplacian matrix ($L = D-A$ where $D$ is the degree matrix and $A$ the adjacency matrix). How can the eigenvectors of $L$ be used, along with ...
Sham's user avatar
  • 1
0 votes
0 answers

Distributed coloring of nodes of sensor ntwork

I have the same graph coloring problem as in Coloring of nodes of a sensor network @RobPratt and @prubin have proposed some very good solutions. This time I am or interested in distributed coloring ...
KGM's user avatar
  • 2,377
0 votes
0 answers

In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?

In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an elementary path, meaning that no vertices are repeated. However, when an elementary path is ...
IsalanOnkar's user avatar
0 votes
0 answers

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following. Given a graph $G = \{V,E\}$, we have a distance matrix (the ...
Yichuan_Sun's user avatar