POLYNOMIAL OBSERVABLES IN THE GRAPH PARTITIONING PROBLEM

M. A. Marchisio ()
Additional contact information
M. A. Marchisio: Dipartimento di Fisica, Università di Trento, I-38050 Povo, Italy

International Journal of Modern Physics C (IJMPC), 2001, vol. 12, issue 01, 13-18

Abstract: 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.

Keywords: Time Complexity; NP-Complete; Redgraph; Redbonds (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183101001456
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:12:y:2001:i:01:n:s0129183101001456

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183101001456

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().