Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
5,106 questions
0
votes
0
answers
19
views
Find the largest subset of chords in which every pair intersects
I have been trying to solve the following problem from ericksons algorithms:
20)c) Let P be a set of n points evenly distributed on the unit circle, and let S be a set of m
line segments with ...
- 1
1
vote
0
answers
20
views
Hypergraph partitioning constrained on partition size
I have a $k-$uniform hypergraph $H=(V,E)$ with $n$ vertices. I need to partition $H$ into two partitions of sizes $r$ and $n-r$. Is there an approximating algorithm that can do this while minimizing ...
- 111
1
vote
1
answer
145
views
Given a tree, find a preorder-like ordering which satisfies additional ordering between nodes
Suppose you have this tree:
0
/ \
1 3
| |
2 4
/ \
5 6
With preorder-like ordering I mean the orderings where the father ...
- 11
0
votes
1
answer
74
views
Counting Number of Complete Binary Trees with n Nodes
I know that the number of different complete binary tree structures (unlabeled) for n nodes is basically 1, because the structure is fixed.
Now I am trying to find the number of labeled complete ...
- 91
1
vote
2
answers
86
views
Looking for Graphs with Known Chromatic Numbers
I’m working on an algorithm for graph coloring, and I want to test how close its results are to the actual chromatic number. For this, I’m looking for graphs whose chromatic numbers are already known.
...
- 47
0
votes
0
answers
25
views
Understanding reduce operations in PyTorch and autodiff. Confused on Operation tracking
I am trying to understand how the Reduce Operation that PyTorch does in its backward pass for broadcasted tensors actually work under the hood. I am trying to make a cpp library for neural networks ...
0
votes
1
answer
90
views
Why does A=A−1 (adjacency matrix squared equals identity) imply that the graph is a perfect matching?
I’m studying properties of adjacency matrices of graphs.
Suppose G
is a simple undirected graph with adjacency matrix $A$
. If we have
$A^2=I$,
where $I$
is the identity matrix, then it seems this ...
- 91
0
votes
1
answer
56
views
partitioning a graph into to single nodes with straight cuts only
Is there an algorithm that can with as few cuts lead to all nodes disconnected? If there is, or an approximation, could someone link me to the paper?
Sorry if there's not enough constraints and seems ...
0
votes
1
answer
85
views
Best mutations for Simulated Annealing on real graph
Here’s what I’m working on: I want to build routes that maximize my custom metrics. I don’t want to share the exact details of these metrics, but for every candidate route I calculate N metrics and I’...
- 1
8
votes
1
answer
1k
views
Switching bodies to get everyone back to their correct body?
Yamada-kun can switch bodies with anyone he kisses. So first he kisses A, and switches into their body. Then, as A, he kisses B and switches into their body (and now B is in A's body). Then, as B, he ...
- 652
1
vote
1
answer
60
views
What does the Minimum Spanning Tree in a Relationship Graph represent?
Say that you have $n$ friends. They each have preference weights for each other. (e.g. the edge between Bob and Alice is 10 and the edge between Bob and Carl is 0.5, meaning that Bob likes/wants to ...
- 652
2
votes
1
answer
105
views
Directed graph for a system of equations
I have a system of equations represented by a directed graph. Each node is a variable. Each edge is a "term dependency" that is a part of one equation. The graph is guaranteed to be ...
- 121
3
votes
1
answer
87
views
Algorithms for embedding a graph on a 2D grid to minimize Manhattan distance between neighbours
I have an undirected, unweighted graph with N vertices. I want to find a 2D embedding of the vertices on a k × n grid (where <...
- 31
1
vote
0
answers
41
views
Deterministic Θ(m + n) SSSP for Arbitrary Positive Real Weights via Monotone Buckets
Context
Dijkstra’s algorithm with a comparison-based heap runs in
Θ(m + n log n) time on a directed graph with non-negative real edge
weights. The freshest bound I’m aware of for real weights is
<...
- 21
2
votes
0
answers
89
views
Given a polynomial time approximation for expected chromatic number of random graph, can we show that P = NP?
Consider an Erdos-Renyi random graph $G(n, p)$. Suppose there exists a coloring algorithm $\mathcal{A}$ that, for any graph instance $g \sim G(n, p)$, generates a valid coloring $C^{\mathcal{A}}_g$ of ...
- 348