Optimum Branching Problem Revisited
From MaRDI portal
Publication:6478249
arXivmath/0611460MaRDI QIDQ6478249FDOQ6478249
Authors: Maxim Babenko, Pavel V. Nalivaiko
Publication date: 15 November 2006
Abstract: Given a digraph , a emph{branching} in is a set of arcs such that the underlying undirected graph spanned by is acyclic and each node in is entered (emph{covered}) by at most one arc from . Tarjan developed efficient algorithms (based on the cycle contraction technique) for the following problem: given a digraph with a emph{weight} function , find a branching of the minimum weight among all branchings with the maximum ardinality . We generalize this notion as follows: for a digraph and a matroid on , a emph{matroid branching} in w.r.t. is a branching in such that the covered set of nodes is independent w.r.t. . The unweighted (cardinality) problem consists in finding a matroid branching with 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 that minimizes (for a given weight function ) among all matroid branchings of the maximum cardinality. We show that if is a rainbow matroid (that is, nodes of are marked with colors and it is forbidden to cover more than one node of any color), then there exists an method, matching the complexity of Tarjan's algorithm (here , ).
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)
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)