This  paper  presents new  graph partitioning  algorithms  for  domain
decomposition-based  simulations whose  subproblems are  solved  using
sparse  direct  factorization  methods (e.g., FETI).  These algorithms
simultaneously balance the number of nodes  assigned to each partition
and produce a fill reducing ordering that balances the fill-in  of the
subdomain matrices, while minimizing the edgecut. Experimental results
from a wide  range of  applications  show that  these  algorithms  can
reduce the fill-in of overweight  subdomains  and achieve considerably
better balance.