Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
0
votes
1answer
10 views
Simple algorithm to generate a linear extension from partial order set
I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.
2
votes
1answer
26 views
All pair shortest path in a tripartite graph
I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
3
votes
0answers
27 views
What is the current fastest algorithm for finding the maximum common subgraph?
First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question.
So, I'm currently researching algorithms for ...
2
votes
2answers
76 views
Negative simple path NP-Complete
Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$
My approach was to ...
-1
votes
0answers
13 views
Find paths between 2 vertices in a Graph
which algorithm can be used to find the paths between two vertices of an unweighted graph ?
I tried to use BFS and DFS to solve this exercise but I'm not sure it could help me complete it.
-1
votes
0answers
19 views
Formula for maximum matching in bipartite graph
Let $G = (U, W, E)$ be a bipartite graph. Show that $\alpha'(G) = \min(|U| - |S| + |N(S)|)$, where $S$ ranges over all subsets of $U$,
$\alpha'(G$) is the size of maximum matching of $G$, and $N(S)$ ...
1
vote
1answer
16 views
Graph partitioning with parts of equal size
Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum.
Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$);...
1
vote
1answer
39 views
Find path from node 1 to N with lowest possible max cost
I have an assignment where I need to find a path from node 1 to node N in an undirected graph given weights in O(E Log^2 E) and using a ...
0
votes
0answers
26 views
Simplification of an objective function of an optimization problem [on hold]
Let $G(V,E)$ be an undirected weighted simple graph, where $V$ and $E$ are the set of vertices and edges. Let $A \in \{0,1\}^{n\times n}$ and $W \in R_+^{n\times n}$ be the adjacency matrix and the ...
0
votes
1answer
19 views
Dijkstra complexity analysis using adjacency list and priority queue?
I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will ...
0
votes
0answers
28 views
Clique number of a graph given its order and average degree
Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree.
Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$.
Find the ...
2
votes
2answers
480 views
Easy instances of the coloring problem on graphs with degree at most 4
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.
In ...
1
vote
1answer
14 views
When is a root node an articulation point in a graph?
I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point.
Based on the literature I'...
0
votes
0answers
11 views
How could the Cuckoo Search be implemented into Python? (Presumably a solver) [closed]
I was looking to do this for just a fun project, and maybe mine some GRIN coin.The proof-of-work for GRIN is the cuck(ar)oo29 algorithm, with 29 nodes in each graph. There is also an ASIC chain, for ...
1
vote
1answer
27 views
Minimum Spanning Tree with one particular edge minimised(continued)
I have recently encountered a coding problem, specifically, the CCC problem S4.
In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
2answers
40 views
Minimum spanning tree such that one edge can be minimised
During a computer coding exam, I have encountered such a problem.
Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
0
votes
0answers
6 views
How to plot moving position of a particle with given time vector in matlab? [closed]
I try to make an animation of plot in Matlab using vector $X$, vector $Y$ and given time vector $T$. There are several examples related to animation and plot with random time and with 'pause(t)'. It ...
4
votes
1answer
52 views
Find all edges in a tree whose removal doesn't separate color classes
Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.
Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.
...
1
vote
2answers
48 views
Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?
Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?
2
votes
1answer
32 views
Name of a tree with arbitrary number of branches at each fork point?
A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.
How do you call a rooted tree if the number of branches per ...
0
votes
0answers
36 views
Generalized graph [closed]
I have N (e.g. 10) attributed multigraphs like this:
They are similar, not same. And i need merge these 10 graphs into 1, which is general.
Use case is: I have one large multigraph, user marks 10 ...
0
votes
0answers
27 views
Number of ways to partition a tree(containing values in its nodes) into groups such that each group has xor sum equal to Z
I tried two approaches:
1. Give each edge two numbers on its left and right side denoting xor sum for subtree on its left and right respectively. If total xor sum for whole tree is Z, then it can only ...
1
vote
0answers
32 views
$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost
I have this problem
A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
0
votes
0answers
19 views
Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?
The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
0
votes
1answer
18 views
Sorting on non-linear topology
Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...
1
vote
1answer
26 views
Path of maximum value with bounded cost in DAG
Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is ...
8
votes
0answers
129 views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
0
votes
0answers
29 views
Contraction Hierarchies minimal distance proof
I am trying to implement "Contraction Hierarchies" algorithm and reading the white paper and watching video lectures [6,7]. But still I can't understand proof for the following lemma:
Lemma 1. $d(s,...
1
vote
1answer
41 views
Shortest path from source to all vertices, but with some wildcards
Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).
You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
4
votes
1answer
40 views
Maximum matching using linear programming
In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ...
0
votes
0answers
26 views
Algorithm for the following graph transformation
Given a directed graph $D = (V,A)$ with edge-weights $w\in\mathbb{R}_{++}^A$ I'm trying to construct the following graph $D'=(V',A')$:
For a fixed $v\in V$ we add a vertex $(v,0)$ to $V'$
For every $(...
1
vote
0answers
45 views
Finding the best state for chain graph with cycles
I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
2
votes
1answer
39 views
List of algorithm problems in term of ideals
I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
1
vote
1answer
28 views
Reduction Vertex cover into Dominating Set
I have a question to the reduction from Vertex Cover into Dominating Set.
So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new ...
4
votes
2answers
75 views
Add lines to star with fixed coordinates maximizing smallest angle
I have the following problem:
There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change....
1
vote
0answers
25 views
How do distributed algorithms for shortest path finding handle negative cycles?
I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
-1
votes
1answer
29 views
Can someone point out why these directed graphs aren't equivalence relations?
As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
3
votes
1answer
59 views
Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$
The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so ...
1
vote
0answers
18 views
Maximizing cache utilization when scheduling a computation graph
So I’m making a program where I generate a computation graph that will be executed on an external device, where the goal is to order the computations in the graph so that the whole computation is done ...
0
votes
1answer
32 views
Minimal edge cover of the hypergraph
We know that minimal edge cover for the normal graph is polynomial time solvable.
Is it also true for hypergraph?
1
vote
0answers
28 views
Proof that G is a Tree After DFS and BFS form the same tree T [closed]
Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth
first search ...
2
votes
1answer
45 views
Djikstra algorithm analysis
My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?
Dijkstra algorithm pseudocode:
...
0
votes
1answer
24 views
set cover to edge cover
I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I ...
0
votes
0answers
8 views
Converting a cyclic digraph to an approximated tree
I have a digraph that represents a taxonomy of sorts, where nodes are "concepts" (i.e., person, animal, plant, etc) and the edges represent an is-a relationship. Hence, we can have ...
6
votes
1answer
123 views
Optimal partitioning of n-tuples
Motivation
Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
4
votes
1answer
67 views
Topological sorting colored tree
EDIT: The most general case I need is not a tree but any Directed Acyclic Graph.
I have a directed acyclic graph.
I need to sort it in a list so that in the list every node comes after any node it ...
0
votes
1answer
21 views
minimum cardinality maximal matching of graph
How to find minimum cardinality maximal matching?
I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
1
vote
1answer
50 views
Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?
John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each ...
1
vote
1answer
47 views
Is there an algorithm to find the minimal number of dimensions, given the distances between points?
Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$
where $\Vert \cdot \Vert$ is the ...
1
vote
0answers
25 views
Searching Algorithm on Connected Graph
This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math.
Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
