Questions tagged [graphs]

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

110 questions
Filter by
Sorted by
Tagged with
81 views

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 ...
29 views

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 ...
232 views

Additional resources for this type of problem formulation

I'm working on a problem with the following formulation: \begin{align} \min&\quad\sum_{i \in N} \sum_{j \in J} V_{ij}x_{ij} \\ \text{s.t.}&\quad \sum_j x_{ij} = 1 \quad \forall i \in N\\ &...
143 views

How to generate random connected planar graph?

I was trying to generate random connected planar graph for dome numerical experiment of some transportation problem. I have three types of nodes: supply, transshipment and demand. I have the number of ...
52 views

updating cliques for an updated graph

A graph $G$ has nodes $V$ and edges $E$. Let's say I have found the maximum clique or all the cliques in $G$ with any algorithm, such as the Bron-Kerbosch algorithm. After a while, $E$ has been ...
1 vote
40 views

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 ...
180 views

Finding Diverse Paths using Constraint Programming

I am working on a graph problem and want to find some link-disjoint paths between given node pairs. I was wondering if there is an efficient way to achieve this in CP. I checked OR-Tools (routing and ...
160 views

34 views

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 ...
89 views

Coloring of nodes in a sensor networks

I have weighted graph for sensor networks with aggregation nodes and sensors. There is a edge between two nodes associated with a weight. Higher the weight, stronger the interference between the ...
1 vote
52 views

Does cutting a minimum spanning tree generate two minimum Steiner tree?

I am trying to understand whether this intuition is true or false. Given a minimum spanning tree (MST) of an undirected positive graph $G=(V,E)$. Consider a MST $T\subseteq G$. Removing any single ...
218 views

Smallest graph coloring in Gurobi

I am trying to design an algorithm to label a graph’s nodes with as few colors as possible such that all pairs of nodes joined by an edge do not have the same color. This is the code I have written so ...
1 vote
148 views

How to perform clustering of a large number of nodes?

I have a clustering problem with around 400-500 nodes. The edge between any two nodes has a weight (between 0 and 1, 0: can be considered as there is no edge/connection between these two nodes) as ...
152 views

Vehicle passenger assignment with capacity constraint

Problem Summary To match passengers (the number of passengers) to capacitated vehicles such that the profit is increased. All the vehicles have the same capacity $c$. It is not important to track ...
172 views

Name of graph algorithm arising while using the Ryan Foster Branching

I'm using the Ryan-Foster branching in my Branch and Price algorithm for a pickup and delivery problem, but I'm having trouble keeping track of all the pairs as I go down the search tree. Let's say ...
152 views

Number of simple cycles on the graph

I would like to know if there is an efficient way to formulate simple cycles on the Graph/Digraph. Let's say, there is a grid-form graph for which each vertex is only connected to a limited number of ...
260 views

How to partition a giant tour into feasible routes?

In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then ...
202 views

Directed trees and the order/score of each node in the tree

Suppose we have a directed tree as follows: The information regarding the edges are also given to us as a list like edge_info = [ (a,c) , (a,b) , (b,d) , (b,e) , (b,f) ] I am trying to find a way to ...
77 views

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 ...
391 views

Is this arc routing formulation correct?

Let $G=(V,E)$ be a graph. I would like to identify an eulerian cycle in $G$ with minimum cost, with an integer programing approach: $x_{ij}$ are integer variables that denote the number of times that ...
1 vote
274 views

Graph models - Maximum flow problem and minimum cost flow problem

I'm trying to solve this problem: An investment agency holds the rights to six investment projects: I1, I2, ..., I6. Projects I1, I2 and I3 are research and technological development projects and the ...
152 views

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 ...
162 views

References for "metric" network flow problems

Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems. Very efficient implementation of state-...
68 views

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(\...
70 views

How to write a constraint to define valid agglomerations of sites?

I am currently attempting to use a MIP to optimize the agglomeration of sites to fit a minimum size. Take for example the following simplified situation of 9 sites which could be any range of sizes. ...
47 views

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 ...
208 views

Flow problem with side constraints: how to eliminate subtours?

I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the ...
324 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
1k views

Is there any way to generate all the possible undirected graphs with unlabeled nodes?

I am looking for an efficient algorithm to generate all of the unique graphs for a given number of nodes. For small instances, the total number of graphs are as follows: n=2 G=2 n=3 G=4 n=4 G=11 ...
206 views

Is this ILP formulation for Group Closeness Centrality a column generation approach?

I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the ...
1k views

Gurobi finishes with 'infeasible' although optimal solution exists

I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs. I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the ...
259 views

Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends

Consider a graph whose vertices can be partitioned into $n$ layers. Edges exist only between vertices in successive layers. So, there are edges between layers $1$ and $2$, between layers $2$ and $3$ ...
90 views

Reformulating undirected to directed edges for MCF

As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges. By quoting them: The ...
94 views

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)$ ...
602 views

How to model Max-Cut as ILP

I want to model Max-Cut in IBM's CPLEX, but I fail at modeling the objective function. My attempt is to use is to sum the XOR of inclusion for vertices of each edge, as exactly then an edge is ...
116 views

Graph Theory problem

I just got sent a problem that I haven't found any model for thus I do not know how to proceed in solving it, if anybody can show me a similar problem so I can use it as a starting point or if they ...