The Inhibiting Bisection Problem [electronic resource].
- Washington, D.C. : United States. Dept. of Energy, 2006.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
- Additional Creators:
- United States. Department of Energy
United States. Department of Energy. Office of Scientific and Technical Information
- Given a graph where each vertex is assigned a generation orconsumption volume, we try to bisect the graph so that each part has asignificant generation/consumption mismatch, and the cutsize of thebisection is small. Our motivation comes from the vulnerability analysisof distribution systems such as the electric power system. We show thatthe constrained version of the problem, where we place either the cutsizeor the mismatch significance as a constraint and optimize the other, isNP-complete, and provide an integer programming formulation. We alsopropose an alternative relaxed formulation, which can trade-off betweenthe two objectives and show that the alternative formulation of theproblem can be solved in polynomial time by a maximum flow solver. Ourexperiments with benchmark electric power systems validate theeffectiveness of our methods.
- Published through SciTech Connect.
19th ACM Symposium on Parallelism in Algorithmsand Architectures, San Diego, CA, June 9-11, 2007.
Pinar, Ali; Lesieutre, Bernard; Fogel, Yonatan.
Ernest Orlando Lawrence Berkeley NationalLaboratory, Berkeley, CA (US)
- Funding Information:
View MARC record | catkey: 14346091