Pith. sign in

REVIEW

Diameter reduction via arc reversal

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2402.06259 v2 pith:EIQJ6ZAZ submitted 2024-02-09 math.CO

classification math.CO
keywords diameterdirectedgraphnumberorientedproblemreversalsalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

The diameter of a directed graph is the maximum distance between any pair of vertices. We study a problem that generalizes \textsc{Oriented Diameter}: For a given directed graph and a positive integer $d$, what is the minimum number of arc reversals required to obtain a graph with diameter at most $d$? We investigate variants of this problem, considering the number of arc reversals and the target diameter as parameters. We show hardness results under certain parameter restrictions, and give polynomial time algorithms for planar and cactus graphs. This work is partly motivated by the relation between oriented diameter and the volume of directed edge polytopes, which we show to be independent.

Discussion (0). Continue with ORCID to comment.

Pith tools