Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs

DOI10.1017/S0963548313000394zbMath1282.05054arXiv1202.2602MaRDI QIDQ5397736

Hao Huang, Jie Ma, Asaf Shapira, Raphael Yuster, Benjamin Sudakov

Publication date: 24 February 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.2602

zbMATH Keywords

minimum feedback arc set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

Related Items (7)

Minimum arc-cuts of normally regular digraphs and Deza digraphs ⋮ Minimum cuts of distance-regular digraphs ⋮ Decomposing tournaments into paths ⋮ Long cycles, heavy cycles and cycle decompositions in digraphs ⋮ Exact localisations of feedback sets ⋮ Note on long paths in Eulerian digraphs ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs

Cites Work

• Unnamed Item
• Retiming synchronous circuitry
• Cycles in dense digraphs
• A proof of a conjecture of Bondy concerning paths in weighted digraphs
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Directed Graphs Without Short Cycles
• Ranking Tournaments

This page was built for publication: Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs