A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given -vertex graph, whether we can remove at most vertices to obtain a bipartite permutation graph. This problem is -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time , and also give a polynomial-time 9-approximation algorithm.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC9304081 | PMC |
| http://dx.doi.org/10.1007/s00453-021-00923-7 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
New clades of viruses infecting the obligatory biotroph representing distinct evolutionary trajectory for viruses infecting oomycetes.
Virus Evol
January 2024
Institute for Sustainable Plant Protection, National Research Council of Italy, Strada Delle Cacce 73, Torino 10135, Italy.
Recent advances in high throughput sequencing (HTS) approaches allowed a broad exploration of viromes from different fungal hosts, unveiling a great diversity of mycoviruses with interesting evolutionary features. The word mycovirus historically applies also to viruses infecting oomycetes but most studies are on viruses infecting fungi, with less mycoviruses found and characterized in oomycetes, particularly in the obligatory biotrophs. We, here, describe the first virome associated to , the causal agent of lettuce downy mildew, which is an important biotrophic pathogen for lettuce production and a model system for the molecular aspects of the plant-oomycetes interactions.
View Article and Find Full Text PDFA Graph-Based Neural Approach to Linear Sum Assignment Problems.
Int J Neural Syst
March 2024
Department of Information Engineering, Università Politecnica delle Marche, Italy.
Linear assignment problems are well-known combinatorial optimization problems involving domains such as logistics, robotics and telecommunications. In general, obtaining an optimal solution to such problems is computationally infeasible even in small settings, so heuristic algorithms are often used to find near-optimal solutions. In order to attain the right assignment permutation, this study investigates a general-purpose learning strategy that uses a bipartite graph to describe the problem structure and a message passing Graph Neural Network (GNN) model to learn the correct mapping.
View Article and Find Full Text PDFQuantum Entanglement and State-Transference in Fenna-Matthews-Olson Complexes: A Post-Experimental Simulation Analysis in the Computational Biology Domain.
Int J Mol Sci
June 2023
School of Engineering and Sciences, Tecnologico de Monterrey, Santa Fe 01389, Mexico.
Fenna-Mathews-Olson complexes participate in the photosynthetic process of Sulfur Green Bacteria. These biological subsystems exhibit quantum features which possibly are responsible for their high efficiency; the latter may comprise multipartite entanglement and the apparent tunnelling of the initial quantum state. At first, to study these aspects, a multidisciplinary approach including experimental biology, spectroscopy, physics, and math modelling is required.
View Article and Find Full Text PDFJoint Entity and Relation Extraction With Set Prediction Networks.
IEEE Trans Neural Netw Learn Syst
September 2024
Joint entity and relation extraction is an important task in natural language processing, which aims to extract all relational triples mentioned in a given sentence. In essence, the relational triples mentioned in a sentence are in the form of a set, which has no intrinsic order between elements and exhibits the permutation invariant feature. However, previous seq2seq-based models require sorting the set of relational triples into a sequence beforehand with some heuristic global rules, which destroys the natural set structure.
View Article and Find Full Text PDFThe probability of edge existence due to node degree: a baseline for network-based predictions.
bioRxiv
January 2023
Department of Systems Pharmacology and Translational Therapeutics, University of Pennsylvania, Philadelphia, Pennsylvania, United States of America.
Important tasks in biomedical discovery such as predicting gene functions, gene-disease associations, and drug repurposing opportunities are often framed as network edge prediction. The number of edges connecting to a node, termed degree, can vary greatly across nodes in real biomedical networks, and the distribution of degrees varies between networks. If degree strongly influences edge prediction, then imbalance or bias in the distribution of degrees could lead to nonspecific or misleading predictions.
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!