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
-1
votes
0answers
18 views

Strongly connected components in adirected graph

Let $G$ be an arbitrary directed graph. Does $G$ always have the same strongly connected components on $G$ as on $G^*$? $G^*$ is the inverted Graph of $G$ ($(u,v)\in E \rightarrow (v,u) \in E^*$). I'...
0
votes
0answers
5 views

How to define the stability (or convergence) of a ordering of a list of node

I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...
2
votes
1answer
50 views

HamiltonianCycles in Random Graphs

Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \{1,2,\cdots,n\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $. Is there anything we can say ...
3
votes
0answers
17 views

Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This ...
-1
votes
0answers
11 views

How to prove of disprove the following Control Flow Graph theory

See the attached image for some background on Control Flow Graph In a single-entry, single-exit control flow graph (CFG), a node u post-lead v if every path from v to the exit includes 𝑢. Let q be ...
0
votes
0answers
13 views

Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names. Some ground-rules: we're traversing in ...
0
votes
1answer
37 views

Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in O(n^2): We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
0
votes
0answers
27 views

Modifying relaxation for the Bellman-Ford algorithm [on hold]

I'm using the Bellman-Ford algorithm to find the best path in my graph. However, instead of choosing the path with the lower value, I want to choose the path with the highest value. And instead of ...
2
votes
1answer
89 views
+50

Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...
0
votes
0answers
13 views

How to transform an arbitrary graph into a fixed vector representation?

Actuality I work in computer vision, specifically on a problem known as "scene graph modeling." This problem aims to convert an image $I$ in a graph $G=(V,E)$ where the nodes $V$ represent the objects ...
1
vote
1answer
27 views

Student Course Allocation Problem with Many Constraints [on hold]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
0
votes
0answers
20 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
1
vote
1answer
27 views

Connected but not adjacent vertex

Is there any specific terms or adjectives in graph theory to name this two situations? Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-...
0
votes
2answers
64 views

Constructing a directed graph for O(1) queries

This question appeared in an undergrad data structures final. The details are sound. I need help to design a data structure for a directed graph with the following properties: Initialization should ...
0
votes
0answers
16 views

Learning the weights in a directed acyclic graph

I have a directed acyclic graph $G=(V,E)$ where each vertex $v$ is associated with a weight $w_v$ such that $$w_v=1+\sum\limits_{(v,v')\in E} w_{v'}$$ and $w_v=1$ in case $v$ is a leaf. I am trying ...
1
vote
1answer
42 views

Does the Bellman-Ford algorithm find all the negative cycles?

The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some? The algorithm really focuses on the shortest paths, so I'm unclear if it ...
4
votes
1answer
565 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
0
votes
0answers
23 views

Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
1
vote
1answer
193 views

Hamilton Circuit

The Dirac's theorem states that: "For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit." Can the same be said if a graph has a Hamilton ...
1
vote
1answer
17 views

Hamiltonian non intersecting path in plane

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
2
votes
0answers
40 views

Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
2
votes
1answer
42 views

Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges. Is the following statement true? If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected....
0
votes
0answers
11 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
1answer
13 views

efficiently calculate nearest common ancestor in a family tree (each person has two parents)

I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent). Just iterate back to root for each ...
0
votes
0answers
40 views

Minimum number of moves to reach a grid point by modified knight in variant chessboard

I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://...
0
votes
2answers
59 views

minimum moves for Knight on a infinite chessboard [duplicate]

You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible. I can ...
1
vote
0answers
30 views

Ordering vertices of graph based on specific vertex-transitivity

Given any complete directed weighted graph $G$ with $n$ vertices and matrix of non-unique weights $W$, find a weak ordering $T(G, W)$ on the vertices of the graph satisfying the following conditions: ...
1
vote
0answers
38 views

Generate Hamiltonian path with obstacles

I want to make some Hamiltonian paths with obstacles in a grid that are hard to find It's for a game that I want to create, which consists of passing from all the cases of the grid without passing ...
0
votes
0answers
14 views

Looking for a similar graph algorithm to generate a graph given the edges a path took

I'm looking for some help on algorithms that may help generate a directed non-cyclic graph from a list of leaf nodes and the incomplete set of edge nodes taken to get to the leaf node. For example, ...
0
votes
1answer
20 views

Algorithm for placing circles of Diameter d around the edge of another circle with diameter D [closed]

Hi i'm struggling with what i think may be simple maths. I need to place circles of a small size around the edge of larger circle.. is there an algorithm to calculate the angle for each small circle ...
1
vote
0answers
25 views

How can we find number of triangles in a given undirected graph? [closed]

If we assume we have n triangles in a given graph. How can we find the n triangles in O(n) time? And we also have to add and remove edges in O(log k) when k=|v|
0
votes
0answers
42 views

Traversing a Graph polynomial time

Given a directed graph $G = (V, E)$ and a starting vertex $v_1$. The graphs edges is this $\{(v_1, v_2), (v_2, v_3), (v_3, v_4)\}$ basically below $(v_1) \to (v_2) \to (v_3) \to (v_4)$ Can we ...
1
vote
1answer
26 views

graph theory conventions, difference between a PATH and a GRAPH?

Consider this example, I did my pseudocode in python findCycle(G): for each edge e in E(G): if isThereCycle(G-e): G = G - e return G ...
0
votes
1answer
28 views

Decomposition of a directed graph into Hamiltonian paths

I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as ...
3
votes
2answers
252 views

Weight functions in graph algorithms

In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$. Why ...
0
votes
0answers
6 views

maximize Steiner vertices in graphs of diameter 3

Let $G=(V, E)$ be a simple connected graph of diameter 3 and $T \subseteq V$ be a set of terminal vertices in $G$. For any $T' \subseteq T$, $(V', E')$ denotes a subgraph of $G$ containing $T',$ ...
2
votes
1answer
44 views

Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must ...
1
vote
1answer
40 views

Finding path with specific length in weighted graph

Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path. ...
1
vote
1answer
35 views

Complexity of K-Colorful Coloring Problem for a Hypergraph

I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem ...
0
votes
0answers
26 views

gas station problem variation

A question from an exam: Input:   A map of a country with distances (in km) on roads. some cities have gas stations.    The map is given in the form of directed ...
1
vote
1answer
34 views

Path of exact cost k in DAG

struggling with this question from an exam: input:   DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $   Two vertices : s,t   Number: k output: ...
0
votes
0answers
21 views

Distribution of number of references to other object in an object

I been thinking about an improvement to a garbage collector (details not important for this question) and wished to know how often does a object have no reference to other objects. Clearly this will ...
2
votes
1answer
46 views

is it always true that the depth of BFS is $\leq$ DFS?

I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS? From what I understand, the tricky part here is the ...
0
votes
0answers
13 views

Fuzzy graph matching to merge disparate data models

I have 2 disparate data models and I want to identify when they are talking about conceptually similar things. All elements are constructed from the same basis set of 60+ observables. Compound ...
0
votes
0answers
9 views

Evaluating clustering/partitioning quality

I'm wondering what are the most common/recognized methods to assess the quality of a clustering. That is because I have developed a tool that can cluster/partition a network (in this case, a public ...
0
votes
0answers
17 views

How to guarantee the minimum path removed from priority queue is the shortest path after all infinite vertices relaxed

I readed the proof of Dijkstra's algorithm in "CLRS",and the code in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. Figure 24.7 in CLRS proofs the correctness of Dijkstra's algorithm. ...
5
votes
1answer
277 views

SAT algorithm for determining if a graph is disjoint

What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint? The best one I can think of is this: Number the nodes 1..N, where N is the number ...
1
vote
1answer
27 views

Finding rainbow cycle in digraph colored with $\log n$ colors [closed]

Given a directed graph with $n$ vertices, and $k=\log n$, we are given a coloring of the vertices with $k$ colors. Describe an algorithm determining if there exists a simple cycle in $G$ of ...
2
votes
0answers
34 views

Many-to-many Breadth First Search

There is a directed social network with large number of nodes and arcs and there are many instances of the network (nodes are same but arcs change in each instance). You can think of it as a ...
1
vote
1answer
38 views

Winning strategy using Dynamic Programing

Let $G=(V,E)$ be a DAG and let $v_0\in V$. Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, ...