Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
180 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,...
1
vote
1answer
194 views

Efficiently generate a random subgraph (Gs) with maximum degree K, using only edges from an existing graph G

I am looking find a way of efficiently generating a random, undirected subgraph $G_s$ with $N$ vertices, using a subset of edges from an exisiting undirected graph $G$, also of size $N$, where the ...
1
vote
0answers
26 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 ...
1
vote
0answers
118 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. ...
1
vote
0answers
43 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 ...
1
vote
0answers
40 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?
0
votes
1answer
117 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 ...
0
votes
1answer
568 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 ...
0
votes
1answer
139 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 ...
0
votes
1answer
212 views

Hypergraph matching -> adjacency matrix?

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?
0
votes
2answers
360 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 ...
0
votes
1answer
148 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. ...
0
votes
1answer
61 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. ...
0
votes
1answer
643 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 ...
0
votes
1answer
87 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.
0
votes
1answer
283 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 ...
0
votes
0answers
21 views

Controllability - Maximum Matching

I found this image on wikipedia referring to Barabasi's work on Network Controllability. I tried to verify it. We have a A matrix of dimensions (20 by 20) made as the image suggests. According to the '...