Covering Directed Graphs by In-Trees

DOI10.1007/978-3-540-69733-6_44MaRDI QIDQ3511356zbMATH OpenOpenAlexFDO

Authors Naoyuki Kamiyama, Naoki Katoh

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_44

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Covering directed graphs by in-trees
• The Minimum Weight In-Tree Cover Problem
• Arc-disjoint in-trees in directed graphs
• scientific article; zbMATH DE number 4212101
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

Cites work

• A weighted matroid intersection algorithm
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximating the minmax rooted-tree cover in a tree
• Approximations for minimum and min-max vehicle routing problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Covering the edge set of a directed graph with trees
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 5764894 (Why is no real title available?)
• scientific article; zbMATH DE number 3659627 (Why is no real title available?)
• Min-max tree covers of graphs.
• Rooted \(k\)-connections in digraphs

Cited in

(7)

• On directed graphs with an independent covering set
• Optimal direct and indirect covering trees
• scientific article; zbMATH DE number 4134096 (Why is no real title available?)
• The Minimum Weight In-Tree Cover Problem
• Covering directed graphs by in-trees
• Arc-disjoint in-trees in directed graphs
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

This page was built for publication: Covering Directed Graphs by In-Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511356)