People who code: we want your input. Take the Survey

Questions tagged [graph-theory]

A field of combinatorics relating to the study of vertices and the edges that connect them

79 questions
Filter by
Sorted by
Tagged with
141 views

Splittable and non-splittable flows in the network flow problem

I am working on a multi-commodity flow problem where for a graph $G=(V, E)$, some flows are permitted to be split and some flows should strictly follow one path. I have formulated this problem as ...
75 views

Does the box-covering algorithm work also for directed graphs?

According to this article from Wikipedia, the box-covering algorithm calculates the fractal dimension of a graph. The algorithm is based on the concept of distance between nodes; see for example the ...
169 views

Measure the differences in vertices density in a graph?

Lets say in Graph $G$ we have two vertices $v$ and $u$, each vertex is connected to several neighbors by edges describing the distances $d_{ij}$ from these neighbors. The neighbors themselves are also ...
791 views

Graph drawing with constraints

I have a (cyclic undirected) graph stored in a suitable structure (which depends on the language chosen). Nodes represent places in the real world and edges represent connection between them, so I ...
181 views

Rearrange a dense distance matrix to a 2x2 non-perfect block diagonal form

I have a distance matrix (square, symmetrical, non-negative, dense). I want to split the objects into two well-connected groups. Mathematically speaking, I want to group (re-arrange) the rows/columns ...
43 views

Is there some algorithm to find the shortest path in the context of genetics and breeding?

In genetics and breeding, we typically have two parent genotype (may or may not be the same) which can produce a set of offspring with certain probability (assuming simple Mendelian inheritance). I ...
16 views

polylog implementation of fully-dynamic graph connected-components?

I have read about papers in the last 20 years that have solved this problem. Many are mentioned in http://jamiemorgenstern.com/teaching/s18-6550/notes/notes-lec4-dgc.pdf Unfortunately the only ...
20 views

Find all recurring subgraphs/patterns of maximal size in a single undirected, labeled, connected graph

I would like to identify all subgraphs of maximal size (maximum number of nodes) that are recurrent in a single undirected, labeled, connected graph. I provide exemples of input and expected output ...
304 views

First approximation to the TSP in a non-complete Graph

I'm trying to solve the Travelling Salesman Problem in a non-complete graph $(G,E)$ using genetic algorithms. My problem is that I can't find a good first approximation by the usual greedy algorithms,...
27 views

Chinese character component-based layout engine algorithms [closed]

I am looking for a PDF describing Chinese character component-based layout engine algorithms. These should allow for recursive encodings of radical and non-radical components, and the encodings should ...
139 views

Updating factorization of Laplacian (add/remove edges)

For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges. ...
47 views

Alternative to two “for” loops in finding best neighborhoods for TSP?

I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!). For the moment I am using ...
43 views

Interior nodes of a closed graph?

Does anybody know if any graph partitioner library such as Metis, Scotch, or Zoltan can (besides splitting a domain), differentiate between internal (i) and boundary (b) nodes?
83 views

What is an instance (precisely) in computational complexity?

I am trying to understand the notion of reduction of a problem to another problem. As it is known this has huge impact on classifying the complexity of a problem. The definition of reduction involves ...
245 views

Finding a shortest path in a graph

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
1k views

Can a Depth first traversal of a graph visit node more than once? [closed]

Is there a way in which Depth First Traversal will put a node into the stack more than once using the general algorithm as shown here. Also, is it compulsory for all nodes to be entered into the ...
142 views

how to partition a graph(matrix) into subdomains with different sizes

i am studying the solver for PageRank problems which drived from the web link graph. I have tried using METIS to divided the matrix into subdomains, but METIS can only produce subdomains with nearly ...
747 views

How to reorder/cluster adjacency matrix to maximize the interaction along the super diagonal?

I have the following code which takes a DataFrame and plot the pdist matrix. ...
354 views

I need to do a matching on a hypergraph. I read that in the case of a hypergraph there is no adjacency matrix. How do I represent edges then?
396 views

How to represent molecules and compare equality

I originally asked this question at StackOverflow, and was suggested to bring it here. I've seen this question about the representation of molecules in memory, and it makes sense to me (tl;dr ...
94 views

Unique Partition of a Graph

Given an undirected graph, is it possible to find a criteria that leads to a unique partition of the nodes? The graph is not weighted.
24 views

Does computing all shortest paths in a simple graph result in a complete graph that follows a metric?

I have a simple graph $G=(V,E)$ that is not necessarily a complete graph. If I compute the shortest distance between every pair of vertices (let say with Floyd-Warshall algorithm) I get a complete ...
64 views

simple and fast graph-clustering for paralelization of finite element simulations

I'm learning to use OpenCL to optimize some of my simulations. I realized that I need some sort of Graph-clustering or graph-partitioning to exploit efficiently local memory for un-ordered meshes. ...
770 views

sparse matrix format with fast row and column access

Is there an efficient storage format for general, non-symmetric sparse matrices for which one can find all non-zero entries in a given row or column in $O(d)$ time? ($d$ is the max number of non-zero ...
285 views

Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
13 views

How can I find the maximum equal-split flow of a network

I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint ...
68 views

How to distinguish primary hosts (stars) and orbiting satellites (planets) and tertiary bodies (moons) by their mass and trajectory?

I posted this question in the astronomy stackexchange. There are no responses, and it was suggested that I pose the question here. The "too long, didn't read" was taken from a comment, and ...
Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...