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
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 ...
• 1
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 ...
• 543
87 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 ...
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 ...
• 2,104
1 vote
64 views

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 ...
• 11
48 views

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 ...
• 2,377
151 views

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 ...
144 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 ...
• 61
38 views

Graphs arcs on AMPL C++ API

I am trying to model a routing instance in AMPL C++ API. The AMPL Book presents a strategy for modeling routing instances via AMPL (Figures 6-2a and 6-2b, Page 95, Chapter 6), as it is presented below:...
93 views

Is there a name for this problem?

Consider a graph $G = (V,E)$ where $V$ is the set of vertices and $E$ is the set of weighted edges. We want to create $N$ disjoint subsets of $V$ such that the sum of weights inside each subset is ...
• 309
292 views

How to do one octomino?

Here are all the 369 octominoes: https://en.wikipedia.org/wiki/Octomino If I have an 8x8 area, how to create one octomino, any of those 369 and any rotation and mirroring is allowed? I have tried ...
• 119
229 views

Graph coloring problem redundant constraints

Say the edges of a 4 nodes graph are 0 1, 1 2 and 1 3. The solution to the colouring problem ...
• 133
106 views

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 ...
• 13.6k
1 vote
82 views

Traffic lights optimization (part 2)

This is a follow up question of this thread, in which it is asked how to model a circular layout of a given set of cliques of a graph, which represent simultaneous movements at an intersection. @...
• 13.6k
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 ...
1 vote
135 views

Coloring of nodes of a sensor network

It is the same problem as posted at Coloring of nodes in a sensor networks. Its about coloring a weighted graph. @RobPratt suggested a very good solution that solves the problem directly. However, we ...
• 2,377
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 ...
• 2,377