a min-凯发官网入口

a min-max relation in flowgraphscarlos e. ferreira1,2institute of mathematics and statisticsuniversity of s˜ ao paulo, s˜ ao paulo, brazil´alvaro j. p. franco1,2ararangu´ a campusfederal university of santa catarina, araranguá, brazilabstractwe have considered the problem of finding vertex-disjoint dipaths in flowgraphs andwe observed an interesting min-max relation: given a flowgraph g, the minimumsize of a dominator cover in g is equal to the maximum size of a junction partitionof g. in many optimization problems those relations are closely related to efficientalgorithms to solve them.keywords: flowgraphs, dominators, junctions, vertex-disjoint dipaths.1 introductionin [2] we described an efficient algorithm that receives an acyclic digraph dand a vertex s of d, and returns a partition b of the set of vertices of d suchthat, taking any pair of vertices {u,v}, u and v are in different parts of b if1supported by cnpq proc. 456792/2014-7 and fapesp proc. 2013/03447-62emails: cef@ime.usp.br, alvaro.junio@ufsc.bravailable online at www.sciencedirect.comelectronic notes in discrete mathematics 50 (2015) 109–1141571-0653/© 2015 elsevier b.v. all rights reserved.www.elsevier.com/locate/endmhttp://dx.doi.org/10.1016/j.endm.2015.07.019