Maximum directed cuts in acyclic digraphs | Zendy

Alon Noga | Zendy; Bollobás Béla | Zendy; Gyárfás András | Zendy; Lehel Jenő | Zendy; Scott Alex | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Maximum directed cuts in acyclic digraphs

Author(s) -

Alon Noga,

Bollobás Béla,

Gyárfás András,

Lehel Jenő,

Scott Alex

Publication year - 2007

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.20215

Subject(s) - digraph , directed acyclic graph , combinatorics , directed graph , mathematics , strongly connected component , feedback arc set , discrete mathematics , constant (computer programming) , graph , computer science , line graph , voltage graph , programming language

It is easily shown that every digraph with m edges has a directed cut of size at least m /4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in acyclic digraphs, and prove a number of related results concerning cuts in digraphs and acyclic digraphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 1–13, 2007

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research