𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Autocorrelation coefficient for the graph bipartitioning problem

✍ Scribed by E. Angel; V. Zissimopoulos

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
858 KB
Volume
191
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Local search and its variants simulated annealing and tabu search are widely used heuristics to approximately solve NP-hard optimization problems. To use local search one "simply" has to specify a neighborhood structure and a cost function which has to be optimized. However, from a theoretical point of view, many questions remain unanswered, and one of the most important is: which neighborhood structure will provide the best quality solutions? The aim of this paper is to theoretically justify some results previously reported by Johnson et al. (1989Johnson et al. ( , 1991) ) in their extended empirical study concerning simulated annealing and the graph bipartitioning problem, and to sharply tune the best landscape among the two reported in that study. Experimental results perfectly agree with the theoretical predictions.

πŸ“œ SIMILAR VOLUMES

On the Ramsey Problem for Multicolor Bip
On the Ramsey Problem for Multicolor Bipartite Graphs
✍ W.A Carnielli; E.L Monte Carmelo πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 85 KB

Given i, j positive integers, let K denote a bipartite complete graph and let i, j ## Ε½ . R m, n be the smallest integer a such that for any r-coloring of the edges of K r a, a one can always find a monochromatic subgraph isomorphic to K . In other m, n Ε½ . Γ„ 4 words, if a G R m, n then every mat

An extremal bandwidth problem for bipart
An extremal bandwidth problem for bipartite graphs
✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 119 KB πŸ‘ 2 views
A polynomial algorithm for the extendabi
A polynomial algorithm for the extendability problem in bipartite graphs
✍ J. Lakhal; L. Litzler πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 587 KB

Let G = [ y E] be a simple connected graph and let k be an integer such that 0 < k < 1 VI /2. G is said to be k-extendable if it contains a perfect matching and every matching of k edges extends to, i.e. is a subset of, a perfect matching. The extendability problem consists in finding the maximum va

Short Solution of Kotzig's Problem for B
Short Solution of Kotzig's Problem for Bipartite Graphs
✍ A.S. Asratian πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 263 KB

In 1975, A. Kotzig posed the following problem: Let G be a t-regular graph which has a proper edge t-coloring, t 4. Is it possible to obtain, from one proper edge t-coloring of G, any other proper edge t-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the inte