Contributions to science:
Contribution 6: Braingraphs
We created the first consensus braingraph server (the Budapest Reference Connectome Server) [6,1]; we proved that women’s braingraphs had better connectivity properties than that of the men [2,5,8,14,17] at the first time in the literature. We have shown that the women’s advantage in brain connectedness is due to sex, and not to the size of their brain [8]. We have mapped the differences in the individual variability of the braingraphs in lobes and in smaller brain areas [3,13], also first in the literature.
We also have recognized – first in the literature – that there is a close connection between the number of occurrences of a certain edge in the braingraphs of different subjects and the time of its development in the prenatal and early infant brain [4,9,10,12].
We have made thousands of braingraphs, computed by us, available to the community [10,11, 20, 22] at the https://braingraph.org site. For artificial intelligence applications, similarly to the Gaussian blurring, we discovered a new augmenting technique, the Newtonian blurring, and applied it for multiplying the already computed braingraphs in [20], with successful applications in artificial intelligence based classifications. The augmented braingraph set contains 631 thousands graphs at https://braingraph.org. We have also discovered a connectome edge-directing method, and published hundreds of high resolution directed connectomes [4, 10, 12], first in the literature.
The large number of braingraphs computed by us, facilitated statistical approaches, which were impossible on smaller cohorts. For example, we were able to find frequently appearing substructures in the graphs of cerebral connections: in [14] we have described the frequently appearing subgraphs of the human braingraph, and identified significant sex differences between their frequencies. In [17] we have described the frequently appearing complete subgraphs in the human connectome, and found 812 complete subgraphs, which are more frequent in male and 224 complete subgraphs, which are more frequent in female connectomes.
We have introduced the Frequent Network Neighborhood Mapping method, and applied it to the neighbors of the human hippocampus to discover cerebral areas which are most frequently connected to the hippocampus. The method identified significant sex- and intelligence differences in hippocampus neighbors in [15,16].
In [12] we have shown the robustness of the Consensus Connectome Dynamics (CCD) phenomenon, and we have also given a probabilistic simulation that well-approximates the CCD phenomenon, also first in the literature.
In publications [19, 21] we focused on single connections of the brain instead of more involved graph theoretical properties. We identified 2 connections in [19], namely the (rh.superiorfrontal, Left-Putamen) and the (rh.parstriangularis, rh.superiorparietal) edges, whose weight are high, then the connectome belongs to a female subject, and, similarly, we have found three edges, such that, if the weights of (lh.rostralmiddlefrontal, Left-Thalamus-Proper) and (Right-Hippocampus, lh.supramarginal) are both high and the weight of (rh.parstriangularis, rh.superiorparietal) is low then the sex of the subject is male. Note that the last edge, with high weight is one of the two which imply female sex.
In [21] we have found 158 connections of the brain, such that from the weight of any of those edges one can predict the sex of the subject with good accuracy.
References:
22, Bálint Varga, Vince Grolmusz: The braingraph.org Database with more than 1000 Robust Human Structural Connectomes in Five Resolutions, Cognitive Neurodynamics Vol. 15 No. 5, pp. 915-919, (2021) https://doi.org/10.1007/s11571-021-09670-5
22, Dániel Hegedűs, Vince Grolmusz: Robust Circuitry-Based Scores of Structural Importance of Human Brain Areas, PLOS One Vol. 19. No. 1 e0292613. https://doi.org/10.1371/journal.pone.0292613 (2024)
21, László Keresztes, Evelin Szögi, Bálint Varga, Vince Grolmusz: Discovering Sex and Age Implicator Edges in the Human Connectome, Neuroscience Letters Vol. 791, 136913 (2022) https://doi.org/10.1016/j.neulet.2022.136913
20, László Keresztes, Evelin Szögi, Bálint Varga, Vince Grolmusz: Introducing and Applying Newtonian Blurring: An Augmented Dataset of 126,000 Human Connectomes at braingraph.org, Scientific Reports, 12:3102 (2022), https://doi.org/10.1038/s41598-022-06697-4
19, László Keresztes, Evelin Szögi, Bálint Varga, Vince Grolmusz: Identifying Super-Feminine, Super-Masculine and Sex-Defining Connections in the Human Braingraph, Cognitive Neurodynamics, Vol. 15. No. 6. pp. 949-959 (2021) https://doi.org/10.1007/s11571-021-09687-w
18, Balázs Szalkai, Bálint Varga, Vince Grolmusz: The Graph of our Mind; Brain Sciences, Vol. 11, No. 3. 342 (2021) https://doi.org/10.3390/brainsci11030342
17, The Frequent Complete Subgraphs in the Human Connectome; Máté Fellner, Bálint Varga, Vince Grolmusz; PLOS ONE 15(8): e0236883 (2020) https://doi.org/10.1371/journal.pone.0236883
16, Good Neighbors, Bad Neighbors: The Frequent Network Neighborhood Mapping of the Hippocampus Enlightens Structural Factors of the Human Intelligence; Máté Fellner, Bálint Varga, Vince Grolmusz; Scientific Reports Vol. 10. 11967 (2020) https://doi.org/10.1038/s41598-020-68914-2
15, The Frequent Network Neighborhood Mapping of the Human Hippocampus Shows Much More Frequent Neighbor Sets in Males Than in Females; Máté Fellner, Bálint Varga, Vince Grolmusz; PLOS ONE 15(1): e0227910 (2020). https://doi.org/10.1371/journal.pone.0227910
14, The Frequent Subgraphs of the Connectome of the Human Brain, M. Fellner, B. Varga, V. Grolmusz; Cognitive Neurodynamics Vol. 13, No.5, pp. 453-460 (2019) https://doi.org/10.1007/s11571-019-09535-y https://rdcu.be/bAHoe
13, Comparing Advanced Graph-Theoretical Parameters of the Connectomes of the Lobes of the Human Brain, B. Szalkai, B. Varga, V. Grolmusz; Cognitive Neurodynamics, Vol. 12, No. 6, pp. 549-559 (2018), https://doi.org/10.1007/s11571-018-9508-y https://rdcu.be/8Gwh
12, The Robustness and the Doubly-Preferential Attachment Simulation of the Consensus Connectome Dynamics of the Human Brain, B Szalkai, B Varga, V Grolmusz, Scientific Reports, Vol. 7, 16118, DOI: 10.1038/s41598-017-16326-0 (2017)
11, The braingraph.org Database of High Resolution Structural Connectomes and the Brain Graph Tools, Csaba Kerepesi, Balázs Szalkai, Bálint Varga, Vince Grolmusz; Cognitive Neurodynamics Vol. 11 No. 5, pp. 483-486 (2017) ;
10, High-Resolution Directed Human Connectomes and the Consensus Connectome Dynamics, Balázs Szalkai, Csaba Kerepesi, Bálint Varga, Vince Grolmusz; PLoS One, Vol. 14 No. 4,: e0215473 (2019) https://doi.org/10.1371/journal.pone.0215473
9, The Dorsal Striatum and the Dynamics of the Consensus Connectomes in the Frontal Lobe of the Human Brain, C Kerepesi, B Varga, B Szalkai, V Grolmusz; Neuroscience Letters, Vol. 673, (2018), pp. 51-55.2018 https://doi.org/10.1016/j.neulet.2018.02.052
8, Brain Size Bias Compensated Graph-Theoretical Parameters are Also Better in Women’s Structural Connectomes, B. Szalkai, B. Varga, V. Grolmusz; Brain Imaging and Behavior Vol. 12, No. 3, pp. 663-673, (2018) http://dx.doi.org/10.1007/s11682-017-9720-0
7, Mapping Correlations of Psychological and Connectomical Properties of the Dataset of the Human Connectome Project with the Maximum Spanning Tree Method; B Szalkai, B Varga, V Grolmusz: Brain Imaging and Behavior Vol. 13, No. 5, pp. 1185-1192 (2019), https://doi.org/10.1007/s11682-018-9937-6 , also available freely at this link
6, Parameterizable Consensus Connectomes from the Human Connectome Project: The Budapest Reference Connectome Server v3.0 B Szalkai, C Kerepesi, B Varga, V Grolmusz, Cognitive Neurodynamics, 11(1), pp. 113-116, http://dx.doi.org/10.1007/s11571-016-9407-z (2017)
5, The Graph of Our Mind, B Szalkai, B Varga, V Grolmusz; Brain Sciences, Vol. 11, No. 3. 342 (2021) https://doi.org/10.3390/brainsci11030342
4, How to Direct the Edges of the Connectomes: Dynamics of the Consensus Connectomes and the Development of the Connections in the Human Brain C Kerepesi, B Szalkai, B Varga, V Grolmusz PLoS One 11(6): e0158680. http://dx.doi.org/10.1371/journal.pone.0158680 , June 30, 2016
3, Comparative Connectomics: Mapping the Inter-Individual Variability of Connections within the Regions of the Human Brain C Kerepesi, B Szalkai, B Varga, V Grolmusz; Neuroscience Letters Vol. 662, pp. 17-21, (2018), https://doi.org/10.1016/j.neulet.2017.10.003;
2, Balázs Szalkai, Bálint Varga, Vince Grolmusz: Graph Theoretical Analysis Reveals: Women’s Brains Are Better Connected than Men’s. PLoS ONE 10(7): e0130045 (2015) http://dx.doi.org/10.1371/journal.pone.0130045
1, Balázs Szalkai, Csaba Kerepesi, Bálint Varga, Vince Grolmusz: The Budapest Reference Connectome Server v2.0, Neuroscience Letters, Vol. 595 (2015), Pages 60-62, http://dx.doi.org/10.1016/j.neulet.2015.03.071
Contribution 5: Artificial intelligence methods in life sciences
Our main interest in AI methods in life sciences is as follows: first we create a good AI classifier for some property, then we investigate the reason, which led the classifier to make the decision. This way we can identify biological attributes, which determine or at least strongly influence the property in question.
In [5] we have described the construction of the Budapest Amyloid Predictor, available at https://pitgroup.org/bap , which assigns either the “amyloidogenic” or the “non-amyloidogenic” label to any hexapeptide queried. The underlying tool is a linear Support Vector Machine (SVM), whose weights help us to create an “amyloidogenecity order” on the 20 amino acids in each of the 6 positions of hexapeptides.
We exploited the transparent structure of the SVM in [5] in the work [9], where, first in the literature, amyloid- and non-amyloid patterns were found among hexapeptides. For example, we have shown that for any independently mutated residue (position marked by “x”), the patterns CxFLWx, FxFLFx, or xxIVIV are predicted to be amyloidogenic, while those of PxDxxx, xxKxEx, and xxPQxx are nonamyloidogenic.
By using the Budapest Amyloid Predictor, we have shown in [13] that it can strongly differentiate the border- and the internal hexamers of β-pleated sheets when screening all the Protein Data Bank-deposited homology-filtered protein structures: more than 30% of internal hexamers of β sheets are predicted to be amyloidogenic, while just outside the border regions, only 3% are predicted as such. This result may elucidate a general protection mechanism of proteins against turning into amyloids.
Another nice application of the Budapest Amyloid Predictor is demonstrated in [15].
In [14] another remarkable property of linear SVMs is exploited: we define a simple graph structure on the 64 million hexapeptides as nodes when two hexapeptides are connected by an edge if they differ by only a single residue. We proved that for any two hexapeptides predicted to be “amyloidogenic” by the BAP predictor, there exists an easily constructible path of length at most 6 that passes through neighboring hexapeptides all predicted to be “amyloidogenic” by BAP. The symmetric statement also holds for non-amyloidogenic hexapeptides.
In [3] we have described the construction of our Hidden Markov Model-based gene-finding webserver MetaHMM https://pitgroup.org/metahmm/, and in publications [1,10,11] applied the method for finding novel enzymes in exotic metagenomes for degrading environmental PAH pollution [11] and novel opine dehydrogenases [10].
A new, very accurate protein sequence annotation tool, based on deep neural networks, was described in the publications [2,4], which is also publicly available at https://pitgroup.org/seclaf/. The tool is capable of predicting the Gene Ontology or the UniProt multi-label functional annotations with very high accuracy (UniProt—into 698 classes—AUC 99.99%; Gene Ontology—into 983 classes—AUC 99.45%).
References:
15, Muntasir Kamal, Levon Tokmakjian, Jessica Knox, Peter Mastrangelo, Jingxiu Ji, Hao Cai, Jakub Wojciechowski, Micael P. Hughes, Kristof Takacs, Xiaoquan Chu, Jianfeng Pei, Vince Grolmusz, Malgorzata Kotulska, Julie Deborah Forman-Kay, Peter J. Roy: A Spatiotemporal Reconstruction of the C. elegans Pharyngeal Cuticle Reveals a Structure Rich in Phase-Separating Proteins, eLife, https://doi.org/10.7554/eLife.79396 (2022)
14, ,László Keresztes, Evelin Szögi, Bálint Varga, Viktor Farkas, András Perczel, Vince Grolmusz: Navigating Homogeneous Paths through Amyloidogenic and Non-Amyloidogenic Hexapeptides, arXiv preprint arXiv 2309.03624 (2023)
13, Kristóf Takács, Bálint Varga, Viktor Farkas, András Perczel, Vince Grolmusz: Opening Amyloid-Windows to the Secondary Structure of Proteins: The Amyloidogenecity Increases Tenfold Inside Beta-Sheets, arXiv preprint arXiv 2210.11842 (2022)
12, Balázs Szalkai, Vince K. Grolmusz, Vince I. Grolmusz: Identifying Combinatorial Biomarkers by Association Rule Mining in the CAMD Alzheimer’s Database, Archives of Gerontology and Geriatrics Vol. 73, pp. 300-307 (2017), https://doi.org/10.1016/j.archger.2017.08.006
11, Kinga K. Nagy, Kristóf Takács, Imre Németh, Bálint Varga, Vince Grolmusz, Mónika Molnár, Beáta G. Vértessy:
Novel enzymes for biodegradation of polycyclic aromatic hydrocarbons identified by metagenomics and functional analysis in short-term soil microcosm experiments, Scientific Reports Vol. 14, No. 11608 (2024) https://doi.org/10.1038/s41598-024-61566-6
10, András Telek, Zsófia Molnár, Kristóf Takács, Bálint Varga, Vince Grolmusz, Gábor Tasnádi, Beáta G. Vértessy: Discovery and biocatalytic characterization of opine dehydrogenases by metagenome mining, Applied Microbiology and Biotechnology 108:0 (2024)
https://doi.org/10.1007/s00253-023-12871-z
9, László Keresztes, Evelin Szögi, Bálint Varga, Viktor Farkas, András Perczel, Vince Grolmusz: Succinct Amyloid and Non-Amyloid Patterns in Hexapeptides, ACS Omega Vol. 7, No. 40, 35532-35537 (2022), https://doi.org/10.1021/acsomega.2c02513
8, László Keresztes, Evelin Szögi, Bálint Varga, Vince Grolmusz: Introducing and Applying Newtonian Blurring: An Augmented Dataset of 126,000 Human Connectomes at braingraph.org, Scientific Reports, 12:3102 (2022), https://doi.org/10.1038/s41598-022-06697-4
7, Balázs Szalkai, Vince Grolmusz: SCARF: A Biomedical Association Rule Finding Webserver, Journal of Integrative Bioinformatics, Vol. 19, No. 1. pp. 20210035, (2022) (an invited paper), https://doi.org/10.1515/jib-2021-0035
6, László Keresztes, Evelin Szögi, Bálint Varga, Vince Grolmusz: Identifying Super-Feminine, Super-Masculine and Sex-Defining Connections in the Human Braingraph, Cognitive Neurodynamics, Vol. 15. No. 6. pp. 949-959 (2021) https://doi.org/10.1007/s11571-021-09687-w
5, Lászlo Keresztes, Evelin Szögi, Bálint Varga, Viktor Farkas, András Perczel and Vince Grolmusz: The Budapest Amyloid Predictor and its Applications, Biomolecules, 11(4) 500, (2021) https://doi.org/10.3390/biom11040500
4, SECLAF: A Webserver and Deep Neural Network Design Tool for Biological Sequence Classification, B Szalkai, V Grolmusz, Bioinformatics, Vol 34, No. 14, pp. 2487-2489 (2018) https://doi.org/10.1093/bioinformatics/bty116
3, Balázs Szalkai, Vince Grolmusz: MetaHMM: A Webserver for Identifying Novel Genes with Specified Functions in Metagenomic Samples; Genomics, Vol. 111, No. 4, pp. 883-885, (2019) https://doi.org/10.1016/j.ygeno.2018.05.016
2, Near Perfect Protein Multi-Label Classification with Deep Neural Networks, B Szalkai, V Grolmusz, Methods Vol. 132, pp. 50-56, (2018), https://doi.org/10.1016/j.ymeth.2017.06.034,
1, The Metagenomic Telescope, B Szalkai, I Scheer, K Nagy, B G Vértessy, V Grolmusz, PLoS One, Vol. 9, No. 7, e101605 (2014).
Contribution 4: PageRank-based protein network analysis
We have applied the PageRank of Google for the evaluation of protein-protein interaction networks, and introduced a modified version (the PageRank, divided by the degree of the node) [1,2,3] that is capable of identifying low-degree important network nodes.
In [3] we settled a question concerning the PageRank of undirected graphs, showing a sufficient and necessary condition which implies that the PageRank is proportional to the degrees of the vertices.
In [4] we have introduced the personalized PageRank to the analysis of the proteomics data: we have shown in a pilot study that personalizing the PageRank computation to measurement results would enlighten deep, functional relations with difficultly measured protein concentrations.
In [1] we have introduced – first time in the literature – the relativized PageRank in the analysis of metabolic networks, and have demonstrated that numerous first-class druggable proteins (including InhA, the protein target of the first-line isoniazid drug in the tuberculosis bacterium’s network or the Roscovitine targets in malaria ) have the highest relativized PageRank in their respective networks. In [2] we have demontrated similar findings in the case of the diabetes.
4, When the Web meets the cell: using personalized PageRank for analyzing protein interaction networks, G Iván, V Grolmusz, Bioinformatics 27 (3), 405-407 (2011)
3, A Note on the PageRank of Undirected Graphs, V Grolmusz, Information Processing Letters 115, 633-634 (2015)
2, Identifying diabetes-related important protein targets with few interacting partners with the PageRank algorithm V Grolmusz, Royal Society Open Science 2 (4), 140252 (2015)
1, Equal opportunity for low-degree network nodes: a PageRank-based method for protein target identification in metabolic graphs, D Banky, G Ivan, V Grolmusz, PLoS One 8 (1), e54204 (2013)
Contribution 3: Data-mining in large biological databases and molecular modeling
We applied data-mining methods for making discoveries in large biological databases. The discoveries involved combinatorial biomarker identification in Alzheimer’s disease {10], protein 3D structure analysis [1,2,4], the construction of the new protein-docking tool „Frigate” [3], the construction of the Metagenomic Telescope [6], and the identification of giant viruses in desert environments [5, 9]. In [2] we have shown that only four (spatial) points in the 3D structure of the large family of serine proteases determine the function of the enzyme in question.
14, László Keresztes, Evelin Szögi, Bálint Varga, Viktor Farkas, András Perczel, Vince Grolmusz: Succinct Amyloid and Non-Amyloid Patterns in Hexapeptides, ACS Omega Vol. 7, No. 40, 35532-35537 (2022), https://doi.org/10.1021/acsomega.2c02513
13, Balázs Szalkai, Vince Grolmusz: SCARF: A Biomedical Association Rule Finding Webserver, Journal of Integrative Bioinformatics, Vol. 19, No. 1. pp. 20210035, (2022) (an invited paper), https://doi.org/10.1515/jib-2021-0035
12, Kristóf Takács, Vince Grolmusz: On the Border of the Amyloidogenic Sequences: Prefix Analysis of the Parallel Beta Sheets in the PDB_Amyloid Collection, Journal of Integrative Bioinformatics, Vol. 19, No. 1.
11, Kristóf Takács, Bálint Varga, Vince Grolmusz: PDB_Amyloid: An Extended Live Amyloid Structure List from the PDB, FEBS Open Bio, Vol. 9, No. 1. pp. 185-190, 2019. https://doi.org/10.1002/2211-5463.12524
10, Identifying combinatorial biomarkers by association rule mining in the CAMD Alzheimer’s database Balazs Szalkai, Vince K. Grolmusz, Vince I. Grolmusz, Archives of Gerontology and Geriatrics, Volume 73, November–December 2017, pp. 300-307
9, The “Giant Virus Finder” discovers an abundance of giant viruses in the Antarctic dry valleys, C Kerepesi, V Grolmusz, Archives of Virology, Vol. 162, No. 6, pp. 1671-1676 (2017) http://dx.doi.org/10.1007/s00705-017-3286-4
8, Life without dUTPase, C Kerepesi, J E Szabó, V Papp-Kádár, O Dobay, D Szabó, V Grolmusz, B G Vertessy; Frontiers in Microbiology, Vol. 7, pp: 1768, (2016)
7, Nucleotide 9-mers Characterize the Type II Diabetic Gut Metagenome; B Szalkai, V Grolmusz, Genomics, Vol. 107 pp. 120-123 (2016),
6, The Metagenomic Telescope, B Szalkai, I Scheer, K Nagy, B G Vértessy, V Grolmusz, PLoS One, Vol. 9, No. 7, e101605 (2014).
5, Giant Viruses of the Kutch Desert, C Kerepesi, V Grolmusz; Archives of Virology, Vol. 161, No.3 pp.721-724, (2016)
4, On the asymmetry of the residue compositions of the binding sites on protein surfaces, G Iván, Z Szabadka, V Grolmusz Journal of Bioinformatics and Computational Biology Vol. 7 No. 6, 931 (2009)
3, Discovery of novel MDR-Mycobacterium tuberculosis inhibitor by new FRIGATE computational screen; C Scheich, Z Szabadka, B Vértessy, V Pütter, V Grolmusz, M Schade, PloS One 6 (12), e28428 (2011)
2, Four spatial points that define enzyme families, G Iván, Z Szabadka, R Ördög, V Grolmusz, G Náray-Szabó; Biochemical and Biophysical Research Communications Vol. 383 No. 4, pp. 417-420 (2009)
1, A hybrid clustering of protein binding sites, G Iván, Z Szabadka, V Grolmusz, FEBS Journal Vol. 277 No. 6, pp. 1494-1502 (2010)
Contribution 2: Extremal set systems modulo composite numbers and their applications
We have falsified a longtime conjecture of Frankl through a construction of mod 6-restricted intersection set systems [1], and found numerous applications [2,3,4] for that surprising construction, involving very fast matrix multiplication and a very dense coding method, called „Hyperdense coding” [4].
6, Vince Grolmusz: A Note on the LogRank Conjecture in Communication Complexity. Mathematics (2023), Vol. 11, 4651. https://doi.org/10.3390/math11224651
5, k-wise Set-Intersections and k-wise Hamming-Distances V Grolmusz, B Sudakov, J. Combin. Theory Ser. A 99 (2002), no. 1, 180–190.
4, Modular Representations of Polynomials: Hyperdense Coding and Fast Matrix Multiplication, V Grolmusz, , IEEE Transactions on Information Theory, 54 (8), 3687-3692 (2008)
3, Computing Elementary Symmetric Polynomials with a Subpolynomial Number of Multiplications, V Grolmusz, SIAM Journal on Computing 32 (6), 1475-1487 (2003)
2, Constructing set systems with prescribed intersection sizes, V Grolmusz, Journal of Algorithms 44 (2), 321-337 (2002)
1, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs, V Grolmusz, Combinatorica 20 (1), 71-86 (2000)
Contribution 1: Communication complexity and circuit complexity
In theoretical computer science, we invented new multiparty communication protocols and lower bounds to the size of Boolean circuits with modular gates. Several of our results appeared the most prestigious FOCS and STOC conferences.
7, Vince Grolmusz: A Note on the LogRank Conjecture in Communication Complexity. Mathematics (2023), Vol. 11, 4651. https://doi.org/10.3390/math11224651
6, Circuits and multi-party protocols, V Grolmusz, Computational Complexity 7 (1), 1-18 (1998)
5,, Lower Bounds for (MOD p, MOD m) Circuits, V Grolmusz, G Tardos, SIAM Journal on Computing 29 (4), 1209-1222 (2000), (also in FOCS’1998).
4, A weight-size trade-off for circuits with mod m gates, V Grolmusz, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing pp. 68-74 (1994) (STOC 1994)
3, The BNS Lower-Bound for Multiparty Protocols Is Nearly Optimal, V Grolmusz, Information and Computation 112 (1), 51-54 (1994)
2, Separating the communication complexities of MOD m and MOD p circuits, V Grolmusz, Journal of Computer and Systems Sciences 51 (2) (1995) (also in FOCS’1992)
1, Incomparability in Parallel Computation; V Grolmusz, P Ragde, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS), Los Angeles 1987, pp. 89-98, also in Discrete Applied Mathematics, Vol. 29 (1990), No. 1. pp. 63–78.