The graph theoretic concept of maximal independent set arises in several practical problems in computer science as well as in game theory. A maximal independent set is defined by the set of occupied nodes that satisfy some packing and covering constraints. It is known that finding minimum and maximum-density maximal independent sets are hard optimization problems. In this paper, we use cavity method of statistical physics and Monte Carlo simulations to study the corresponding constraint satisfaction problem on random graphs. We obtain the entropy of maximal independent sets within the replica symmetric and one-step replica symmetry breaking frameworks, shedding light on the metric structure of the landscape of solutions and suggesting a class of possible algorithms. This is of particular relevance for the application to the study of strategic interactions in social and economic networks, where maximal independent sets correspond to pure Nash equilibria of a graphical game of public goods allocation.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1103/PhysRevE.80.061136 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Differential Effects of the Type of Physical Exercise on Blood Pressure in Independent Older Adults.
Sports Health
January 2025
Instituto Politécnico de Viana do Castelo; Research Center in Sports Performance, Recreation, Innovation and Technology (SPRINT - IPVC), Viana do Castelo, Portugal.
Background: Exercise and its effect on cardiovascular diseases have been extensively studied in the elderly population. The difference in blood pressure (BP) between fit and unfit subjects can be >5 mmHg. It is not well established whether the positive effects of exercising on BP are associated with exercise type, be it aerobic or anaerobic (maximal muscle strength).
View Article and Find Full Text PDFBasic Science and Pathogenesis.
Alzheimers Dement
December 2024
Department of Pathology and Laboratory Medicine, Perelman School of Medicine, University of Pennsylvania, Philadelphia, PA, USA.
Background: The H1/H2 haplotype on 17q21.31 represent the foremost genetic factor contributing to the risk of progressive supranuclear palsy (PSP). Various structural forms of 17q21.
View Article and Find Full Text PDFBasic Science and Pathogenesis.
Alzheimers Dement
December 2024
University of Oregon, Eugene, OR, USA.
Background: Stiffening of the large arteries is a hallmark feature of vascular aging and is associated with cognitive impairment and Alzheimer's disease pathology. Increased large artery stiffness leads to higher-than-normal pulse pressure in the cerebral circulation, damaging endothelial cells. It is known that short-term exposure to stiffer large arteries causes cerebral artery endothelial dysfunction and hypoperfusion in young mice.
View Article and Find Full Text PDFThe Role of WNT5a and TGF-β1 in Airway Remodelling and Severe Asthma.
Allergy
January 2025
Department of Respiratory Sciences, College of Life Sciences, and NIHR Biomedical Research Centre (Respiratory Theme), Glenfield Hospital, Leicester, UK.
Background: Airway remodelling is a feature of severe asthma with airway epithelial damage observed frequently. We evaluated the role of WNT5a and TGF-β in asthmatic airway biopsies and in sputum and bronchial brushings assessed their role in remodelling.
Methods: WNT5a and TGF-β protein expression were assessed in the lamina propria epithelium of people with asthma (GINA 1-3, n-8 and GINA 4-5, n-14) and healthy subjects (n-9), alongside relevant remodelling markers.
Removal of a fractured file beyond the apical foramen using robot-assisted endodontic microsurgery: a clinical report.
BMC Oral Health
January 2025
Department of Endodontics, School of Stomatology, Capital Medical University, Beijing, China.
Background: Endodontic file fractures are common complications of root canal treatment, and requires removal via specialized techniques such as endodontic microsurgery when the file beyond the apical foramen. It is often challenging to precisely and minimally remove a fractured file. Recently the use of dental autonomous robotic system (ATR) has shown promise in precisely and minimally in dental surgery.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!