A rooted-forest partition with uniform vertex demand

• Bérczi K, Frank A (2009) Packing arborescences. Technical Report 2009-04, EGRES

• Berg A, Jordán T (2003) Algorithms for graph rigidity and scene analysis. In: Proceedings of the 11th annual European symposium on algorithms (ESA). Lecture notes in computer science, vol 2832. Springer, Berlin, pp 78–89

  Google Scholar 

• Crapo H (1990) On the generic rigidity of plane frameworks. Technical report, Institut National de Recherche en Informatique et en Automatique

• Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. In: Guy R, Hanani H, Sauer N, Schönheim J (eds) Combinatorial structures and their applications. Gordon and Breach, New York, pp 69–87

  Google Scholar 

• Edmonds J (1973) Edge disjoint branchings. In: Rustin B (ed) Combinatorial algorithms. Algorithmics Press, New York, pp 91–96

  Google Scholar 

• Fekete Z, Szegö L (2004) A note on [k,l]-sparse graphs. In: Graph theory in Paris; a conference in memory of Claude Berge, pp 169–177

  Google Scholar 

• Frank A, Szegö L (2003) Constructive characterizations for packing and covering with trees. Discrete Appl Math 131(2):347–371

  Article  MathSciNet  MATH  Google Scholar 

• Fujishige S (2010) A note on disjoint arborescences. Combinatorica. doi:10.1007/s00493-010-2518-y

  MathSciNet  Google Scholar 

• Gabow H, Tarjan R (1988) A linear-time algorithm for finding a minimum spanning pseudoforest. Inform Process Lett 27(5):259–263

  Article  MathSciNet  MATH  Google Scholar 

• Gabow H, Westermann H (1992) Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7(1):465–497

  Article  MathSciNet  MATH  Google Scholar 

• Haas R (2002) Characterizations of arboricity of graphs. Ars Combin 63:129–138

  MathSciNet  MATH  Google Scholar 

• Hakimi S (1965) On the degrees of the vertices of a directed graph. J Franklin Inst 279(4):290–308

  Article  MathSciNet  MATH  Google Scholar 

• Haller K, Lee A, Sitharam M, Streinu I, White N (2009) Body-and-cad geometric constraint systems. In: Proceedings of the 25th ACM symposium on applied computing. ACM, New York, pp 1127–1131

  Chapter  Google Scholar 

• Imai H (1983) Network flow algorithms for lower truncated transversal polymatroids. J Oper Res Soc Japan 26(3):186–210

  MathSciNet  MATH  Google Scholar 

• Jackson B, Jordán T (2009) Graph theoretic techniques in the analysis of uniquely localizable sensor networks. In: Mao G, Fidan B (eds) Localization algorithms and strategies for wireless sensor networks. IGI Global, Hershey, pp 146–173

  Chapter  Google Scholar 

• Kamiyama N, Katoh N, Takizawa A (2009) Arc-disjoint in-trees in directed graphs. Combinatorica 29(2):197–214

  MathSciNet  MATH  Google Scholar 

• Katoh N, Tanigawa S (2009) On the infinitesimal rigidity of bar-and-slider frameworks. In: Proceedings of the 20th international symposium on algorithms and computation (ISAAC 2009). Lecture notes in computer science, vol 5878. Springer, Berlin, pp 524–533

  Google Scholar 

• Laman G (1970) On graphs and rigidity of plane skeletal structures. J Eng Math 4(4):331–340

  Article  MathSciNet  MATH  Google Scholar 

• Lee A, Streinu I (2008) Pebble game algorithms and sparse graphs. Discrete Math 308(8):1425–1437

  Article  MathSciNet  MATH  Google Scholar 

• Nash-Williams C (1961) Edge-disjoint spanning trees of finite graphs. J Lond Math Soc 1(1):445–450

  Article  MathSciNet  Google Scholar 

• Oxley J (1992) Matroid Theory. Oxford University Press, London

  MATH  Google Scholar 

• Pym J, Perfect H (1970) Submodular functions and independence structures. J Math Anal Appl 30(1–31):33

  MathSciNet  Google Scholar 

• Recski A (1988) Network theory approach to the rigidity of skeletal structures. Part ii. Laman’s theorem and topological formulae. Discrete Appl Math 8(1):63–68

  Article  MathSciNet  Google Scholar 

• Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin

  MATH  Google Scholar 

• Streinu I, Theran L (2009) Sparsity-certifying graph decompositions. Graphs Combin 25(2):219–238

  Article  MathSciNet  MATH  Google Scholar 

• Sugihara K (1985) Detection of structural inconsistency in systems of equations with degrees of freedom and its applications. Discrete Appl Math 10(3):297–312

  Article  MathSciNet  MATH  Google Scholar 

• Tay T (1984) Rigidity of multi-graphs. I: Linking rigid bodies in n-space. J Combin Theory Ser B 36(1):95–112

  Article  MathSciNet  MATH  Google Scholar 

• Tay T (1989) Linking (n−2)-dimensional panels in n-space II: (n−2,2)-frameworks and body and hinge structures. Graphs Combin 5(1):245–273

  Article  MathSciNet  MATH  Google Scholar 

• Tay T (1993) A new proof of Laman’s theorem. Graphs Combin 9(2):365–370

  Article  MathSciNet  MATH  Google Scholar 

• Tutte WT (1961) On the problem of decomposing a graph into n connected factors. J Lond Math Soc 36:221–230

  Article  MathSciNet  MATH  Google Scholar 

• Whiteley W (1988) The union of matroids and the rigidity of frameworks. SIAM J Discrete Math 1(2):237–255

  Article  MathSciNet  MATH  Google Scholar 

• Whiteley W (2005) Counting out to the flexibility of molecules. Phys Biol 2:S116–S126

  Article  Google Scholar 

Download references