Questions tagged [reduction-graphs]

Graph reduction implements an efficient version of non-strict evaluation, an evaluation strategy where the arguments to a function are not immediately evaluated

Filter by
Sorted by
Tagged with
0 votes
0 answers

Graph reduction and combinatorial optimization

Crossposted at Theoretical Computer Science SE We are given a multigraph $G$. Consider two nodes $u$ and $v$ with multiple edges between them. Each elementary edge is associated with a metric called ...
user avatar
  • 521
2 votes
1 answer

How to conclude good reduction from $\mathcal{P} \nmid m$?

I am working on the proof of the main Theorem of complex multiplication states in "Advanced topics in the arithemtics of elliptic curves" of J.Silverman. We have the following situation: $K$ is a ...
user avatar
  • 41
3 votes
1 answer

reduction to np hard ordering problem

I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm. My problem is: I have M auctions and in each auction I have N ...
user avatar
  • 31
0 votes
1 answer

Minimum number of edges - directed graph with given sums of weights

Let's consider a directed graph with positive edge weights. For every vertex we determine the difference D = (summary weight of edges directed FROM this vertex)-(summary weight of edges directed ...
user avatar
  • 3
2 votes
2 answers

Relating the toric rank of a semistable curve and the first Betti number of its reduction graph

Introduction Let $k$ be a local field. Let $C$ be the spectrum of $\mathcal{O}_{k}$. Let $X/k$ be a smooth projective curve with a semistable model $\mathcal{X}/C$. Let $J$ be the Jacobian of $X$. ...
user avatar
  • 5,234