Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

Filter by
Sorted by
Tagged with
0
votes
0answers
2 views

Ranking (k-best) or genetic coding for spanning arborescences

I am wondering if there is a simpler way to rank spanning arborescences or any way to code spanning arborescences genetically. According to the comment by @BearAqua in my another question, min ...
0
votes
1answer
18 views

How to build a graph of people where node connections are determined by name and age?

I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question): Given a list of Pesrons, and two ...
0
votes
0answers
15 views

Time complexity for computing the highest degree vertex

Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the ...
1
vote
1answer
32 views

How to find a cut in a graph with additional constraints?

I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$. I would ...
0
votes
0answers
11 views

How to cluster a dataset in which each data point is composed of a set of 2-dimensional coordinates

I have a dataset with totally $1000$ scenarios, each of which is composed of $5$ users' coordinates $(x_i,y_i), \forall i \in \{1,\dots,5\}$. Now, based on users' coordinates, I want to cluster these $...
0
votes
0answers
13 views

Relationships between centrality metrics?

I am studying graph centrality, and came across a very nice table in here (reproducing it below, all credit goes to the original authors Shaikh Arifuzzaman and Md Hasanuzzaman Bhuiyan). I have ...
0
votes
0answers
14 views

Various implementations of adjacency list representation of a Graph

Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways: Array of arrays (...
1
vote
0answers
38 views

Oriented undirected edges in directed graph

I have a graph with $n$ vertices and $m$ edges. Some edges are already oriented, some are not. How do I determine how to orient all undirected edges so that each vertex has the same outgoing and ...
-1
votes
1answer
20 views

Checking whether there is cycle of odd length in a k-coloring undirected graph

Also, what is the meaning of the notation used in the question- c: v->{0,1,2....k-1} such that c(u)!=c(v)?
1
vote
0answers
16 views

Proof that “the last vertex in any postordering (in a DFS) of G lies in a source component of G”

From the book Algorithms (Jeff Erickson), there's a lemma that states: The last vertex in any postordering of G lies in a source component of G My initial reaction to this was that the proof would ...
-2
votes
0answers
26 views

Сyclic routes in the table

In a $n × m$ table, some cells are locked. How to determinate time whether it is possible to split the remaining cells into cyclic routes of length at least $3$? All unremoved cells must participate ...
1
vote
0answers
18 views

Can Johnson's algorithm for simple cycles be modified in order to find only cycles up to length L (but all of them)?

I have a question regarding Johnson’s algorithm for finding all simple cycles in a graph. I was wondering it is possible to modify the algorithm in order to find only cycles up to a given length. ...
1
vote
0answers
35 views

Finding the smallest-cost way to deliver goods

I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...
1
vote
1answer
90 views

Reducing a problem to the MST problem

Let $G = (V, E)$ be a connected, undirected graph. Given a subset of distinct vertices $S = \{v_1, v_2, \ldots, v_n\} \subseteq V$, how can I find a forest in which each vertex $v \in V - S$ is ...
4
votes
1answer
180 views

The same outgoing and incoming degree in graph

I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same ...
0
votes
1answer
44 views

Bipartite maximum matching with added constraints

Suppose you have two lists as follows List $A$ = $(a_1, a_2, ..., a_m)$ List $B$ = $(b_1, b_2, ..., b_n)$ Each element in list $A$ can be paired with many or no elements in list $B$. I have a function ...
0
votes
1answer
42 views

3SAT and directed graph

Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
5
votes
4answers
184 views

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
2
votes
0answers
19 views

Comparing Directed Unweighted Graphs with Different “Densities” [closed]

I'm looking to compare 2 unweighted directed graphs and get an (ideally differentiable) similarity score. Both graphs describe a trajectory in a 2d space. The reference graph is a step by step guide ...
2
votes
0answers
22 views

How to calculate delta Q (modularity increase matrix) in graphs?

I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
2
votes
1answer
104 views

How to detect “tree-able” set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
4
votes
1answer
180 views

Game on the graph with matchings

The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
0
votes
0answers
28 views

Problem with the algorithm

I am trying to execute the following algorithm shown in the image from my course slide. I am trying to get the table shown in the image: 1st Iteration L2: 1:CS=A, SL = A, NSL = A L3: while NSL!=[]: ...
1
vote
1answer
17 views

Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
-1
votes
1answer
11 views

Maximal vs maximum matchings

Let $M_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M_2$ a maximum-size matching in $G$. How to prove that $|M_2| \le 2|M_1|$?
1
vote
1answer
38 views

Independent sets into which all the vertices of the graph can be split

How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?
0
votes
0answers
10 views

Which algorithm suits best for AST pattern matching

I want to create a refactoring/analysis for java tool in Haskell. I can write the monadic parser, but I don't have clarity about next steps. I could express AST transformations via functions and built-...
0
votes
0answers
23 views

Set of cycles in directed graph

I have a directed graph. How to find in it some set of cycles that are pairwise do not intersect, but cover the entire set of vertices, if a cycle from one vertex is not considered a cycle, but cycle ...
-2
votes
0answers
41 views

How many shortest paths are there from source to destination for Dijkstra's algorithm?

Given an acyclic, directed, and weighted graph. Now how can I determine how many shortest paths are there from source to destination, if i use Dijkstra's algorithm?
0
votes
1answer
20 views

Randomly generating graph based off number of connections on each node

I'm trying to generate a graph based off some data I have. This graph should have N nodes where the number of edges each node has is equal to a random number ...
0
votes
1answer
23 views

What is a dominator node and a dominator tree?

I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node: a node d dominates a node n if every path from the entry node to n must go ...
-1
votes
1answer
32 views

Prove following statement about Kruskal Algorithm

Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
2
votes
1answer
21 views

Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?

MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem is to find a ...
1
vote
1answer
43 views

Proof of lemma for flow in residual graph

In CLRS 3'rd edition there is a Lemma 26.2 which states that: Let $G=(V, E)$ be a flow network, let $f$ be a flow in $G,$ and let $p$ be an augmenting path in $G_{f}$. Define a function $f_{p}\colon ...
0
votes
0answers
6 views

How to extract the buildings bottom surfaces from a large city 3D mesh?

I have a 3D mesh comprised of city buildings, no ground surface, just buildings. The goal is to extract the buildings bottom surfaces. So far I have tried to cut the mesh by a threshold computed from ...
0
votes
0answers
20 views

Kruskal naive implementation: how to use DFS to detect cycle in MST plus next edge?

Most discussion of naive (without Union-Find) implementations of Kruskal's algorithm for finding the minimal spanning tree that I see has a handwavy bit: "just use DFS to detect if there is a ...
3
votes
1answer
53 views

Find a maximum matching that saturates a given set of vertices

In an unweighted bipartite graph $G = (X + Y,E)$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset $X_0\subseteq ...
6
votes
0answers
505 views

What could we say about that conjecture that yields P != NP?

Let $F$ be the set of all Boolean formulae. We say that a Boolean formula $\varphi$ is positive (=monotone) if $\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
3
votes
0answers
55 views

Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
1
vote
1answer
15 views

Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints

I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are ...
3
votes
1answer
244 views

efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
0
votes
0answers
50 views

Algorithm to color the edges of the square of a cycle

It is known that any power of cycle on even vertices is in Class 1, that is, can be edge colored in $\Delta$ colors, where $\Delta$ is its maximum degree which equals twice the power. But, I wish to ...
0
votes
1answer
80 views

Google Foobar Level 4 - Graph Problem

So, I have been solving problems in Google Foobar for the past two weeks or so ans has reached Level 4. The first problem is as stated below and I have come up with a solution which is able to pass ...
3
votes
1answer
52 views

Topological sort where some nodes can't come in between two other nodes

I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node ...
1
vote
0answers
28 views

Finding homotopies in a 2-complex

Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?
3
votes
0answers
45 views

Total weight of all spanning trees

Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
0
votes
0answers
28 views

Minimum spanning tree of multi directed graph

Solved. This is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm). I have problem of inferring a rooted tree out of a connected ...
0
votes
1answer
30 views

what would be the time complexity of DBSCAN algorithm?

what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?
0
votes
0answers
20 views

Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
0
votes
0answers
17 views

Problem in UVa 1229 (graph - SCC)

I am solving UVa--1229 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=671&page=show_problem&problem=3670 From the problem I have understood what is required ...

1
2 3 4 5
76