AI Article Synopsis
- - The Minimum Vertex Weighted Coloring (MinVWC) problem is a complex extension of the NP-hard Minimum Vertex Coloring (MinVC) problem, focusing on minimizing the weights of colors assigned to a graph's vertices rather than just the number of colors.
- - The paper introduces a new reduction algorithm that uses maximal clique enumeration to efficiently create smaller subgraphs which can help solve the MinVWC problem without the computational heaviness of branching.
- - Experimental results show that this new algorithm significantly reduces the size of subgraphs for large graphs compared to an existing method, RedLS, and the authors prove that their algorithm's reduction effectiveness matches that of a more exhaustive approach given enough runtime.
Article Abstract
The Minimum Vertex Weighted Coloring (MinVWC) problem is an important generalization of the classic Minimum Vertex Coloring (MinVC) problem which is NP-hard. Given a simple undirected graph G=(V,E), the MinVC problem is to find a coloring s.t. any pair of adjacent vertices are assigned different colors and the number of colors used is minimized. The MinVWC problem associates each vertex with a positive weight and defines the weight of a color to be the weight of its heaviest vertices, then the goal is the find a coloring that minimizes the sum of weights over all colors. Among various approaches, reduction is an effective one. It tries to obtain a subgraph whose optimal solutions can conveniently be extended into optimal ones for the whole graph, without costly branching. In this paper, we propose a reduction algorithm based on maximal clique enumeration. More specifically our algorithm utilizes a certain proportion of maximal cliques and obtains lower bounds in order to perform reductions. It alternates between clique sampling and graph reductions and consists of three successive procedures: promising clique reductions, better bound reductions and post reductions. Experimental results show that our algorithm returns considerably smaller subgraphs for numerous large benchmark graphs, compared to the most recent method named RedLS. Also, we evaluate individual impacts and some practical properties of our algorithm. Furthermore, we have a theorem which indicates that the reduction effects of our algorithm are equivalent to that of a counterpart which enumerates all maximal cliques in the whole graph if the run time is sufficiently long.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC10606255 | PMC |
| http://dx.doi.org/10.3390/e25101376 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Modeling transcriptional regulation of the cell cycle using a novel cybernetic-inspired approach.
Biophys J
January 2024
The Davidson School of Chemical Engineering, Purdue University, West Lafayette, Indiana. Electronic address:
Quantitative understanding of cellular processes, such as cell cycle and differentiation, is impeded by various forms of complexity ranging from myriad molecular players and their multilevel regulatory interactions, cellular evolution with multiple intermediate stages, lack of elucidation of cause-effect relationships among the many system players, and the computational complexity associated with the profusion of variables and parameters. In this paper, we present a modeling framework based on the cybernetic concept that biological regulation is inspired by objectives embedding rational strategies for dimension reduction, process stage specification through the system dynamics, and innovative causal association of regulatory events with the ability to predict the evolution of the dynamical system. The elementary step of the modeling strategy involves stage-specific objective functions that are computationally determined from experiments, augmented with dynamical network computations involving endpoint objective functions, mutual information, change-point detection, and maximal clique centrality.
View Article and Find Full Text PDFIterated Clique Reductions in Vertex Weighted Coloring for Large Sparse Graphs.
Entropy (Basel)
September 2023
Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA.
Article Synopsis
- - The Minimum Vertex Weighted Coloring (MinVWC) problem is a complex extension of the NP-hard Minimum Vertex Coloring (MinVC) problem, focusing on minimizing the weights of colors assigned to a graph's vertices rather than just the number of colors.
- - The paper introduces a new reduction algorithm that uses maximal clique enumeration to efficiently create smaller subgraphs which can help solve the MinVWC problem without the computational heaviness of branching.
- - Experimental results show that this new algorithm significantly reduces the size of subgraphs for large graphs compared to an existing method, RedLS, and the authors prove that their algorithm's reduction effectiveness matches that of a more exhaustive approach given enough runtime.
Unlabelled: Quantitative understanding of cellular processes, such as cell cycle and differentiation, is impeded by various forms of complexity ranging from myriad molecular players and their multilevel regulatory interactions, cellular evolution with multiple intermediate stages, lack of elucidation of cause-effect relationships among the many system players, and the computational complexity associated with the profusion of variables and parameters. In this paper, we present an elegant modeling framework based on the cybernetic concept that biological regulation is inspired by objectives embedding entirely novel strategies for dimension reduction, process stage specification through the system dynamics, and innovative causal association of regulatory events with the ability to predict the evolution of the dynamical system. The elementary step of the modeling strategy involves stage-specific objective functions that are computationally-determined from experiments, augmented with dynamical network computations involving end point objective functions, mutual information, change point detection, and maximal clique centrality.
View Article and Find Full Text PDFA differentiable approach to the maximum independent set problem using dataless neural networks.
Neural Netw
November 2022
University of Colorado Boulder, 440 UCB, Boulder, CO 80309, USA.
The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures.
View Article and Find Full Text PDFMeta-Analysis of Esophageal Cancer Transcriptomes Using Independent Component Analysis.
Front Genet
October 2021
Laboratory of Bioinformatics and Systems Biology, National Laboratory Astana, Center for Life Sciences, Nazarbayev University, Nur-Sultan, Kazakhstan.
Independent Component Analysis is a matrix factorization method for data dimension reduction. ICA has been widely applied for the analysis of transcriptomic data for blind separation of biological, environmental, and technical factors affecting gene expression. The study aimed to analyze the publicly available esophageal cancer data using the ICA for identification and comprehensive analysis of reproducible signaling pathways and molecular signatures involved in this cancer type.
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!