Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Bipartite Graph
Graph Partitioning
Integer Program
Quadratic Program
Linear Program
Subscribe
Academic
Publications
Linear and quadratic programming approaches for the general graph partitioning problem
Linear and quadratic programming approaches for the general graph partitioning problem,10.1007/s1089800995201,Journal of Global Optimization,Neng F
Edit
Linear and quadratic programming approaches for the general graph partitioning problem
(
Citations: 6
)
BibTex

RIS

RefWorks
Download
Neng Fan
,
Panos M. Pardalos
The
graph partitioning
problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zeroone quadratic programming problem without the input of cardinalities. We also present three equivalent zeroone linear integer programming reformulations. Because of its importance in data biclustering, the
bipartite graph
partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.
Journal:
Journal of Global Optimization
, vol. 48, no. 1, pp. 5771, 2010
DOI:
10.1007/s1089800995201
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
hdl.handle.net
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
Citation Context
(5)
...The graph partitioning problem has been studied for a long time and recently studied by linear and quadratic programming approaches [
6
]...
...given cardinalities nk(k = 1, ··· , K). For general graph partitioning [
6
], nk is not necessarily to be given and only required to satisfy nk > 1; For equal partitioning, nk ∈ {� N/K� , � N/K� + 1} with total ∑k nk = N. In CNP, we also delete exactly K vertices to minimize the pairwise connectivity between the remaining vertices...
...In graph partitioning, the paper [
6
] has discussed how to obtain K and presented that the cardinalities n1, ··· , nK can be relaxed to an interval region [Cmin,Cmax]...
Neng Fan
,
et al.
Robust Optimization of Graph Partitioning and Critical Node Detection ...
...For minimum cut (Definition 5) of graph partitioning, the determination of K is studied in
Fan and Pardalos (2010)
by introducing a penalty function...
...For minimum cut (Definition 5) of graph partitioning, the cardinalities are always chosen as equals N/K (Karisch and Rendl 1998; Lisser and Rendl 2003), pregiven integers (Wolkowicz and Zhao 1996; Hager and Krylyuk 2002) or values in a range (
Fan and Pardalos 2010
)...
...titioning by minimum cut (
Fan and Pardalos 2010
)...
...The graph partitioning requiring the given cardinalities n1 ,...,n K can be solved by the approaches of linear programming (Lisser and Rendl 2003;
Fan and Pardalos 2010
), quadratic programming (Fan and Pardalos 2010; Hager and Krylyuk 2002) and semidefinite programming (Lisser and Rendl 2003; Karisch and Rendl 1998; Wolkowicz and Zhao 1996)...
...The graph partitioning requiring the given cardinalities n1 ,...,n K can be solved by the approaches of linear programming (Lisser and Rendl 2003; Fan and Pardalos 2010), quadratic programming (
Fan and Pardalos 2010;
Hager and Krylyuk 2002) and semidefinite programming (Lisser and Rendl 2003; Karisch and Rendl 1998; Wolkowicz and Zhao 1996)...
...In practice, the antidegeneracy constraints (
Fan and Pardalos 2010
) are always added to reduce the computational time...
Neng Fan
,
et al.
Multiway clustering and biclustering by the Ratio cut and Normalized ...
...For K biclusters, Dhillon [17] used kmeans algorithm [31, 57] after obtaining the indicator vector y, and another direct approach is from [
23
] by defining an indicator matrix...
Neng Fan
,
et al.
Recent Advances of Data Biclustering with Application in Computational...
...For more information about alternative clustering approaches, see Tan et al. (2007),
Fan and Pardalos (2010)
...
Flor A. Espinoza
,
et al.
Using Hierarchical Clustering and Dendrograms to Quantify the Clusteri...
...Usually, K is chosen from {2, ··· , N − 1} .A s shown in [
3
,4], the size nk for subset k can be loosely chosen in a range...
...As stated in [
3
,5], many mathematical programming methods, including linear programming, quadratic programming, and semidefinite programming, are used for this problem...
...All generated weights satisfy w ij , c s ∈ [2,
3
] for (vi, v j) ∈ E. The number N(N − 1)r/2 of decision variables y ij s is related to the number of edges, which is related to N, r; the number N(N − 1)rS/ 2o fz s s is determined by N, r, s; and the number N · K · S of x s s is determined N, S, K. In Theorem 2, the variables u s k s are introduced, and the number of u s k s is N(N − 1)rKS/2...
Neng Fan
,
et al.
On the TwoStage Stochastic Graph Partitioning Problem
References
(27)
Global Optimization: Fractal Approach and Nonredundant Parallelism
(
Citations: 4
)
Roman G. Strongin
,
Yaroslav D. Sergeyev
Journal:
Journal of Global Optimization
, vol. 27, no. 1, pp. 2550, 2003
An improved linearization strategy for zeroone quadratic programming problems
(
Citations: 6
)
Hanif D. Sherali
,
Jonathan Cole Smith
Journal:
Optimization Letters
, vol. 1, no. 1, pp. 3347, 2007
Recent directions in netlist partitioning: a survey
(
Citations: 112
)
C. J. Alpert
,
A. B. Kahng
Journal:
Integration
, 1996
Compact Mathematical Formulation for Graph Partitioning
(
Citations: 7
)
Marc Boulle
Journal:
Optimization and Engineering  OPTIM ENG
, vol. 5, no. 3, pp. 315333, 2004
RankTwo Relaxation Heuristics for MAXCUT and Other Binary Quadratic Programs
(
Citations: 56
)
Samuel Burer
,
Renato D. C. Monteiro
,
Yin Zhang
Journal:
Siam Journal on Optimization  SIAMJO
, vol. 12, no. 2, pp. 503521, 2002
Sort by:
Citations
(6)
Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
(
Citations: 1
)
Neng Fan
,
Panos M. Pardalos
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 170183, 2010
Municipal tertiary treatment: Disc filters enhanced by pleated configuration
Miguel Gutierrez
Journal:
Filtration & Separation  FILTR SEP
, vol. 46, no. 5, pp. 2224, 2009
Multiway clustering and biclustering by the Ratio cut and Normalized cut in graphs
(
Citations: 2
)
Neng Fan
,
Panos M. Pardalos
Journal:
Journal of Combinatorial Optimization  JCO
, pp. 128
Recent Advances of Data Biclustering with Application in Computational Neuroscience
(
Citations: 4
)
Neng Fan
,
Nikita Boyko
,
Panos M. Pardalos
Using Hierarchical Clustering and Dendrograms to Quantify the Clustering of Membrane Proteins
Flor A. Espinoza
,
Janet M. Oliver
,
Bridget S. Wilson
,
Stanly L. Steinberg
Journal:
Bulletin of Mathematical Biology  BULL MATH BIOL
, pp. 122