Polynomial observables in the graph partitioning problem

被引：1
|
作者：
Marchisio, MA [1 ]
机构：
[1] Univ Trent, Dipartimento Fis, I-38050 Trent, Italy
来源：
INTERNATIONAL JOURNAL OF MODERN PHYSICS C | 2001年 / 12卷 / 01期
关键词：
D O I：
10.1142/S0129183101001456
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Although NP-Complete problems are the most difficult decisional problems, it is possible to discover in them polynomial (or easy) observables. We study the Graph Partitioning Problem showing that it is possible to recognize in it two correlated polynomial observables. The particular behavior of one of them with respect to the connectivity of the graph suggests the presence of a phase transition in partitionability.
引用
收藏
页码：13 / 18
页数：6
相关论文
共 50 条
  • [1] A POLYNOMIAL CHARACTERIZATION OF SOME GRAPH PARTITIONING PROBLEMS
    ARBIB, C
    INFORMATION PROCESSING LETTERS, 1988, 26 (05) : 223 - 230
  • [2] A polynomial algorithm for balanced clustering via graph partitioning
    Evaristo Caraballo, Luis
    Diaz-Banez, Jose-Miguel
    Kroher, Nadine
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 289 (02) : 456 - 469
  • [3] Revisiting the Isoperimetric Graph Partitioning Problem
    Danda, Sravan
    Challa, Aditya
    Sagar, B. S. Daya
    Najman, Laurent
    IEEE ACCESS, 2019, 7 : 50636 - 50649
  • [4] Efficient Algorithms for a Graph Partitioning Problem
    Vaishali, S.
    Atulya, M. S.
    Purohit, Nidhi
    FRONTIERS IN ALGORITHMICS (FAW 2018), 2018, 10823 : 29 - 42
  • [5] An approximating polynomial algorithm for a sequence partitioning problem
    Kel'manov A.V.
    Khamidullin S.A.
    Journal of Applied and Industrial Mathematics, 2014, 8 (02) : 236 - 244
  • [6] CONTRIBUTION OF COPOSITIVE FORMULATIONS TO GRAPH PARTITIONING PROBLEM
    Povh, Janez
    PROCEEDINGS OF THE 10TH INTERNATIONAL SYMPOSIUM ON OPERATIONAL RESEARCH SOR 09, 2009, : 117 - 127
  • [7] An efficient memetic algorithm for the graph partitioning problem
    Philippe Galinier
    Zied Boujbel
    Michael Coutinho Fernandes
    Annals of Operations Research, 2011, 191 : 1 - 22
  • [8] Semidefinite programming relaxations for the graph partitioning problem
    Wolkowicz, Henry
    Zhao, Qing
    Discrete Applied Mathematics, 1999, 96-97 : 461 - 479
  • [9] Contribution of copositive formulations to the graph partitioning problem
    Povh, Janez
    OPTIMIZATION, 2013, 62 (01) : 71 - 83
  • [10] Metaheuristics for the Minimum Gap Graph Partitioning Problem
    Bruglieri, Maurizio
    Cordone, Roberto
    COMPUTERS & OPERATIONS RESEARCH, 2021, 132
12345