Optimum Branching Problem Revisited

From MaRDI portal
Publication:6478249

arXivmath/0611460MaRDI QIDQ6478249FDOQ6478249


Authors: Maxim Babenko, Pavel V. Nalivaiko Edit this on Wikidata


Publication date: 15 November 2006

Abstract: Given a digraph G=(VG,AG), a emph{branching} in G is a set of arcs BsubseteqAG such that the underlying undirected graph spanned by B is acyclic and each node in G is entered (emph{covered}) by at most one arc from B. Tarjan developed efficient algorithms (based on the cycle contraction technique) for the following problem: given a digraph G with a emph{weight} function wcolonAGoR, find a branching B of the minimum weight w(B):=sumainBw(a) among all branchings with the maximum ardinality absB. We generalize this notion as follows: for a digraph G and a matroid calMV on VG, a emph{matroid branching} in G w.r.t. calMV is a branching in G such that the covered set of nodes is independent w.r.t. calMV. The unweighted (cardinality) problem consists in finding a matroid branching B with absB maximum. We show that the general cycle contraction approach is applicable to this problem and leads to an efficient algorithm (provided that an oracle is given for testing independence in the matroids arising as the result of the contraction procedure). In the weighted version we are looking for a matroid branching B that minimizes w(B) (for a given weight function wcolonAGoR) among all matroid branchings of the maximum cardinality. We show that if calMV is a rainbow matroid (that is, nodes of G are marked with colors and it is forbidden to cover more than one node of any color), then there exists an O(min(n2,mlogn)) method, matching the complexity of Tarjan's algorithm (here n:=absVG, m:=absAG).













This page was built for publication: Optimum Branching Problem Revisited

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