@article{2591, abstract = {The occurrence and distribution of the preferred receptor for the neuropeptide, substance P (SP), the neurokinin-1 receptor (NK1R) was investigated in the vascular supply of the rat sciatic nerve. Messenger RNA for NK1R was demonstrated by RT-PCR in the epineurial layer where the majority of small arteries and arterioles feeding the endoneurial vasculature are located. Immunoreactivity to NK1R-protein was localized on the smooth muscle cells of these arterial vessels by means of immunofluorescence using a polyclonal NK1R antiserum. This muscular localization of NK1R explains the previously reported [Zochodne, D.W. and Ho, L.T., J. Physiol. 444 (1991) 615- 630] moderate vasoconstrictor rather than vasodilator effects of SP in this vascular bed.}, author = {Kummer, Wolfgang and Shigemoto, Ryuichi and Haberberger, Rainer}, issn = {0304-3940}, journal = {Neuroscience Letters}, number = {2}, pages = {119 -- 122}, publisher = {Elsevier}, title = {{Smooth muscle cells are the site of neurokinin-1 receptor localization in the arterial supply of the rat sciatic nerve}}, doi = {10.1016/S0304-3940(98)00926-4}, volume = {259}, year = {1999}, } @article{2592, abstract = {Metabotropic glutamate receptors (mGluRs) consist of eight different subtypes and exert their effects or second messengers and ion channels via G- proteins. The function of individual mGluR subtypes in the CNS, however, largely remains to be clarified. We examined the fear response of freezing after electric shock in wild-type and mGluR7(-/-) knockout littermates. Wild- type mice displayed freezing immediately after and 1 d after footshock. In comparison, mGluR7(-/-) knockout mice showed significantly reduced levels in both immediate postshock and delayed freezing responses. However, the knockout mice exhibited no abnormalities in pain sensitivity and locomotor activity. To further examine amygdala-dependent behavior, we performed conditioned taste aversion (CTA) experiments. In wild-type mice, the administration of saccharin followed by intraperitoneal injection of the malaise-inducing agent LiCl resulted in an association between saccharin and LiCl. This association caused strong CTA toward saccharin n contrast, mGluR7(-/-) knockout mice failed to associate between the taste and the negative reinforcer in CTA experiments. Again, the knockout mice showed no abnormalities in taste preference and in the sensitivity to LiCl toxicity. These results indicate that mGluR7 deficiency causes an impairment of two distinct amygdala-dependent behavioral paradigms. Immunohistochemical and immunoelectron-microscopic analyses showed that mGluR7 is highly expressed in amygdala and preferentially localized at the presynaptic axon terminals of glutamatergic neurons. Together, these findings strongly suggest that mGluR7 is involved in neural processes subserving amygdala-dependent averse responses.}, author = {Masugi, Miwako and Yokoi, Mineto and Shigemoto, Ryuichi and Muguruma, Keiko and Watanabe, Yasuyoshi and Sansig, Gilles and Van Der Putten, Herman and Nakanishi, Shigetada}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {3}, pages = {955 -- 963}, publisher = {Society for Neuroscience}, title = {{Metabotropic glutamate receptor subtype 7 ablation causes deficit in fear response and conditioned taste aversion}}, doi = {10.1523/JNEUROSCI.19-03-00955.1999}, volume = {19}, year = {1999}, } @article{2593, abstract = {In cat and monkey, lamina I cells can be classified into three basic morphological types (fusiform, pyramidal, and multipolar), and recent intracellular labeling evidence in the cat indicates that fusiform and multipolar lamina I cells are two different types of nociceptive cells, whereas pyramidal cells are innocuous thermoreceptive-specific. Because earlier observations indicated that only nociceptive dorsal horn neurons respond to substance P (SP), we examined which morphological types of lamina I neurons express receptors for SP (NK-1r). We categorized NK-1r- immunoreactive (IR) lamina I neurons in serial horizontal sections from the cervical and lumbar enlargements of four monkeys. Consistent results were obtained by two independent teams of observers. Nearly all NK-1r-IR cells were fusiform (42%) or multipolar (43%), but only 6% were pyramidal (with 9% unclassified). We obtained similar findings in three monkeys in which we used double-labeling immunocytochemistry to identify NK-1r-IR and spinothalamic lamina I neurons retrogradely labeled with cholera toxin subunit b from the thalamus; most NK-1r-IR lamina I spinothalamic neurons were fusiform (48%) or multipolar (33%), and only 10% were pyramidal. In contrast, most (~75%) pyramidal and some (~25%) fusiform and multipolar lamina I spinothalamic neurons did not display NK-1r immunoreactivity. These data indicate that most fusiform and multipolar lamina I neurons in the monkey can express NK-1r, consistent with the idea that both types are nociceptive, whereas only a small proportion of lamina I pyramidal cells express this receptor, consistent with the previous finding that they are nonnociceptive. However, these findings also indicate that not all nociceptive lamina I neurons express receptors for SP.}, author = {Yu, Xiao and Zhang, En and Craig, Arthur and Shigemoto, Ryuichi and Ribeiro Da Silva, Alfredo and De Koninck, Yves}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {9}, pages = {3545 -- 3555}, publisher = {Society for Neuroscience}, title = {{NK-1 receptor immunoreactivity in distinct morphological types of lamina I neurons of the primate spinal cord}}, doi = {10.1523/JNEUROSCI.19-09-03545.1999}, volume = {19}, year = {1999}, } @article{2594, abstract = {Substance P receptor (i.e. NK1)-like immunoreactive (SPR-LI) neurons were observed in the newborn and adult human spinal cord. Substance P receptor-like immunoreactive neuronal cell bodies were seen most frequently in lamina I, and were scattered throughout the remaining laminae of the dorsal horn and the area around the central canal. Some neurons in the intermediolateral nucleus also showed weak immunoreactivity. The pattern of distribution of SPR-LI neurons in the adult spinal cord was essentially the same as that in the newborn spinal cord. However, SPR-LI neurons cell bodies were seen much more frequently in the newborn than in the adult dorsal horn, especially in lamina II.}, author = {Ding, Yu and Zheng, Heng and Wang, Dian and Xu, Jun and Gong, Liang and Lü, Yan and Qin, Bing and Shi, Juan and Li, Hua and Li, Ji and Shigemoto, Ryuichi and Kaneko, Takeshi and Mizuno, Noboru}, issn = {0304-3940}, journal = {Neuroscience Letters}, number = {2}, pages = {133 -- 136}, publisher = {Elsevier}, title = {{The distribution of substance P receptor (NK1)-like immunoreactive neurons in the newborn and adult human spinal cord}}, doi = {10.1016/S0304-3940(99)00283-9}, volume = {266}, year = {1999}, } @article{2595, abstract = {Presynaptic metabotropic glutamate receptors (mGluRs) of group III constitute possible targets for putative neuroprotective drugs acting against glutamate excitotoxic insults. Indeed, in glutamatergic cerebellar granule neurones in culture, high concentrations of L-2-amino-4-phosphonobutyrate (L-AP4, above 0.3 mM, thus activating mGluR7) inhibit NMDA-induced cell death. In contrast, in striatal cultures which are enriched in GABAergic neurones, we show that high concentrations of L-AP4 increased neuronal death in control as well as in NMDA-stimulated cultures. Moreover, similar results were obtained with the GABA(B)R agonist, baclofen. Both the neuroprotective effects in cerebellar granule cells and the neurotoxic effects in striatal neurones were mediated via Gi-Go-coupled mGluRs, suggesting that these effects were probably mediated by mGluR7a or b and GABA(B)R expressed in these neurones. In striatal neurones, we found that L-AP4 and baclofen inhibited both basal and NMDA-stimulated GABA release. These inhibitions of GABA release may be responsible for the increase in basal and NMDA-stimulated neuronal death. Indeed, blockade of GABA(A) receptors with bicuculline increased neuronal death of control and NMDA-treated striatal cultures. Taken together, these results suggest that L-AP4 and baclofen, via mGluR7 and GABA(B)R, reduced the neuroprotective effect of GABA present in striatal cultures acting via GABA(A) receptors. Although caution must be taken when extrapolating from in vitro to in vivo situations, the present experiments and the recent observations that mGluR7 and GABA(B)R are expressed in heterologous synapses, should be taken into consideration when evaluating the neuroprotective action of future mGluR7 specific agonists or GABA(B)R specific antagonists.}, author = {Lafon Cazal, Mireille and Viennois, Gaëlle and Kühn, Rainer and Malitschek, Barbara and Pin, Jean and Shigemoto, Ryuichi and Bockaërt, Joël}, issn = {0028-3908}, journal = {Neuropharmacology}, number = {10}, pages = {1631 -- 1640}, publisher = {Elsevier}, title = {{mGluR7-like receptor and GABA(B) receptor activation enhance neurotoxic effects of N-methyl-D-aspartate in cultured mouse striatal GABAergic neurones}}, doi = {10.1016/S0028-3908(99)00124-0}, volume = {38}, year = {1999}, } @article{2596, abstract = {A γ-aminobutyric acid (GABA)(B) receptor (named GABA(B)R1) has been recently cloned in the rat and human brain and two variants generated by alternative RNA splicing were identified. In the present study, we addressed the question as to whether these variants contribute to the diversity of GABA(B) receptor-mediated physiological responses and constitute real receptor subtypes with distinct functions. To this aim, we have mapped the GABA(B)R1 (R1a) and GABA(B)R1b (R1b) transcript distribution in the rat brain using in situ hybridization. We have compared the mRNA distribution with the distribution of [ 3H]CGP54626-labeled binding GABA(B)R1 receptor sites as assessed in adjacent cryosections by quantitative autoradiography. We found that GABA(B) receptor transcripts and binding sites are expressed in the brain in almost all neuronal cell populations. Expression in glial cells, if any, is marginal. We observed a good parallelism between GABA(B)R1 mRNA transcripts and binding sites in broad neuroanatomical entities with highest densities in hippocampus, thalamic nuclei, and cerebellum. By contrast, R1a and R1b transcripts exhibit marked differences in their regional and cellular distribution pattern. A typical example is the cerebellum with an almost exclusive expression of R1b in the Purkinje cells and of R1a in the granule, stellate, and basket cells. Data pointing at a pre- versus postsynaptic localization for R1a and R1b, respectively, at some neuronal sites are presented. }, author = {Bischoff, Serge and Leonhard, Sabine and Reymann, Nicole and Schuler, Valérie and Shigemoto, Ryuichi and Kaupmann, Klemens and Bettler, Bernhard}, issn = {0021-9967}, journal = {Journal of Comparative Neurology}, number = {1}, pages = {1 -- 16}, publisher = {Wiley-Blackwell}, title = {{Spatial distribution of GABA(B)R1 receptor mRNA and binding sites in the rat brain^}}, doi = {10.1002/(SICI)1096-9861(19990913)412:1<1::AID-CNE1>3.0.CO;2-D}, volume = {412}, year = {1999}, } @article{2597, abstract = {Metabotropic glutamate receptors (mGlus) are known to modulate synaptic transmission in various pathways of the central nervous system, but the exact mechanisms by which this modulation occurs remain unclear. Here we utilise electrophysiological and immunocytochemical techniques on cultured autaptic hippocampal neurones to investigate the mechanism of action and distribution of mGlus. Agonists at all three groups of mGlus depressed glutamatergic transmission, whereas only agonists at group I mGlus depressed GABAergic transmission. Agonists at all mGlus failed to modulate Ca2+ and K+ channels in glutamatergic autapses whereas an agonist at group III mGlus did depress the frequency of miniature excitatory postsynaptic currents (mEPSCs). Agonists failed to modulate Ca2+ or K+ channels and miniature inhibitory postsynaptic currents (mIPSCs) in GABAergic autapses. Distribution studies using selective antibodies revealed punctate staining for group III mGlus that co-localised with the synaptic marker, synaptophysin. Staining for the remaining mGlus was more diffuse throughout the soma and processes with little co-localisation with synaptophysin. The distribution of the group III receptors is consistent with the direct 'downstream' modulation of mEPSCs, although the exact mechanism of action for the remaining receptors remains unclear.}, author = {Bushell, Trevor and Lee, Chong and Shigemoto, Ryuichi and Miller, Richard}, issn = {0028-3908}, journal = {Neuropharmacology}, number = {10}, pages = {1553 -- 1567}, publisher = {Elsevier}, title = {{Modulation of synaptic transmission and differential localisation of mGlus in cultured hippocampal autapses}}, doi = {10.1016/S0028-3908(99)00103-3}, volume = {38}, year = {1999}, } @inproceedings{2711, abstract = {We study the long time evolution of a quantum particle in a Gaussian random environment. We show that in the weak coupling limit the Wigner distribution of the wave function converges to the solution of a linear Boltzmann equation globally in time. The Boltzmann collision kernel is given by the Born approximation of the quantum scattering cross section.}, author = {Erdös, László}, booktitle = {Proceedings of the 7th QMath Conference}, isbn = {9783034897549}, location = {Prague, Czech Republik}, pages = {233 -- 242}, publisher = {World Scientific Publishing}, title = {{Linear Boltzmann equation as the weak coupling limit of the random Schrödinger equation}}, doi = {10.1007/978-3-0348-8745-8_20}, volume = {108}, year = {1999}, } @article{2730, abstract = {We give the leading order semiclassical asymptotics for the sum of the negative eigenvalues of the Pauli operator (in dimension two and three) with a strong non-homogeneous magnetic field. This result can be used to prove that the magnetic Thomas-Fermi theory gives the leading order ground state energy of large atoms. We develop a new localization scheme well suited to the anisotropic character of the strong magnetic field. We also use the basic Lieb-Thirring estimate obtained earlier (1996). (orig.) 19 refs.}, author = {Erdös, László and Solovej, Jan}, issn = {0012-7094}, journal = {Duke Mathematical Journal}, number = {1}, pages = {127 -- 173}, publisher = {Duke University Press}, title = {{Semiclassical eigenvalue estimates for the Pauli operator with strong nonhomogeneous magnetic fields, I: Nonasymptotic Lieb-Thirring-type estimate}}, doi = {10.1215/S0012-7094-99-09604-7}, volume = {96}, year = {1999}, } @article{2783, abstract = {Pattern formation in a layer of fluid heated from below is an example of macroscopic ordering in continuous media. Here we show that in a relatively compact experimental version of the problem, a rich and diverse set of stable flows can be found. These flows, many of which are novel, can be categorized and understood in terms of their symmetry properties. This approach shows promise for providing insight into the more complicated fluid motion that occurs as the lateral dimension of the layer is increased.}, author = {Hof, Björn and Lucas, Peter and Mullin, Tom}, issn = {0031-9171}, journal = {Physics of Fluids}, number = {10}, pages = {2815 -- 2817}, publisher = {American Institute of Physics}, title = {{Flow state multiplicity in convection}}, doi = {10.1063/1.870178 }, volume = {11}, year = {1999}, } @article{2864, abstract = {Using an electrospray tandem mass spectrometer as a concentration-sensitive detector, a method has been developed to quantify femtomole amounts of plant growth regulators (i.e. isoprenoid type cytokinins, zeatin, dihydrozeatin, isopentenyladenine and their respective riboside and glucoside analogues) and the second messenger adenosine 3':5'-cyclic monophosphate (3':5'-cAMP). Miniaturisation of the chromatographic setup using capillary high performance liquid chromatographic (HPLC) ion spray mass spectrometry increased the sensitivity to the low femtomole region. Application of automated capillary column switching allowed the introduction of large injection volumes into the HPLC system. Aliquots (25 μL) were injected into one dimension of the HPLC set-up and stacked onto a micro pre-column. By means of mobile phase switching the pre-column was back-flushed to introduce the analytes onto the analytical column. For cytokinin analysis positive electrospray ionisation was used and resulted in 2.5-25 fmol detection limits. Cyclic nucleotides were separated under ion-pair conditions using tetrabutyl ammonium bromide as ion-pair reagent and were detected under negative electrospray ionisation conditions. Here a 25 fmol detection limit was determined. Following this approach, cytokinins and 3':5'-cAMP extracted from only mg amounts of apical shoot meristem and chloroplasts obtained from Nicotiana tabacum cv. Petit Havana SR1 were identified and quantified.}, author = {Witters, Erwin and Vanhoutte, Koen and Dewitte, Walter and Macháčková, Ivana and Benková, Eva and Van Dongen, Walter and Esmans, Eddy and Van Onckelen, Henri}, issn = {0958-0344}, journal = {Phytochemical Analysis}, number = {3}, pages = {143 -- 151}, publisher = {Wiley-Blackwell}, title = {{Analysis of cyclic nucleotides and cytokinins in minute plant samples using phase system switching capillary electrospray liquid chromatography tandem mass spectrometry}}, doi = {10.1002/(SICI)1099-1565(199905/06)10:3<143::AID-PCA441>3.0.CO;2-G}, volume = {10}, year = {1999}, } @article{2865, abstract = {Although cytokinins (CKs) affect a number of processes connected with chloroplasts, it has never been rigorously proven that chloroplasts contain CKs. We isolated intact chloroplasts from tobacco (Nicotiana tabacum L. cv SR1) and wheat (Triticum aestivum L. cv Ritmo) leaves and determined their CKs by liquid chromatography/tandem mass spectroscopy. Chloroplasts from both species contained a whole spectrum of CKs, including free bases (zeatin and isopentenyladenine), ribosides (zeatin riboside, and isopentenyladenosine), ribotides (isopentenyladenosine-5′-monophosphate, zeatin riboside-5′-monophosphate, and dihydrozeatin riboside-5′-monophosphate), and N-glucosides (zeatin-N 9-glucoside, dihydrozeatin-N 9-glucoside, zeatin-N 7-glucoside, and isopentenyladenine-N-glucosides). In chloroplasts there was a moderately higher relative amount of bases, ribosides, and ribotides than in leaves, and a significantly increased level ofN 9-glucosides of zeatin and dihydrozeatin. Tobacco and wheat chloroplasts were prepared from leaves at the end of either a dark or light period. After a dark period, chloroplasts accumulated more CKs than after a light period. The differences were moderate for free bases and ribosides, but highly significant for glucosides. Tobacco chloroplasts from dark-treated leaves contained zeatin riboside-O-glucoside and dihydrozeatin riboside-O-glucoside, as well as a relatively high CK oxidase activity. These data show that chloroplasts contain a whole spectrum of CKs and the enzymatic activity necessary for their metabolism. }, author = {Benková, Eva and Witters, Erwin and Van Dongen, Walter and Kolář, Jan and Motyka, Václav and Brzobohatý, Břetislav and Van Onckelen, Henri and Macháčková, Ivana}, issn = {0032-0889}, journal = {Plant Physiology}, number = {1}, pages = {245 -- 251}, publisher = {American Society of Plant Biologists}, title = {{Cytokinins in tobacco and wheat chloroplasts. Occurrence and changes due to light/dark treatment}}, doi = {10.1104/pp.121.1.245}, volume = {121}, year = {1999}, } @book{3137, abstract = {This volume provides an overview of glutamate receptors and their role in excitatory neurotransmission. It focusses on three aspects. First, it describes the functional, molecular, and pharmacological properties of glutamate receptors (AMPA, NMDA, and kainate receptors). Second, it gives a survey how these receptors are involved in synaptic transmission at different glutamatergic synapses in the mammalian CNS. Finally, it adresses how overactivation of glutamate receptors can lead to excitotoxic cell death, and emphasizes the importance of glutamate receptors as potential therapeutical targets. The chapters, written by leading scientists, give accurate summaries of facets that have emerged recently in this field. The book demonstrates the strength of a multidisciplinary approach involving physiology, pharmacology, and molecular biology. It will be useful for other scientists in and outside the field, lecturers and students at different educational levels.}, editor = {Jonas, Peter M and Monyer, Hannah}, isbn = {978-3-642-08539-0}, issn = {1865-0325}, pages = {XXII, 535}, publisher = {Springer}, title = {{Ionotropic Glutamate Receptors in the CNS}}, doi = {10.1007/978-3-662-08022-1}, volume = {141}, year = {1999}, } @article{3148, abstract = {Accurate proteolytic processing of neuropeptide and peptide hormone precursors by members of the kexin/furin family of proteases is key to determining both the identities and activities of signaling peptides. Here we identify amontillado (amon), the Drosophila melanogaster homolog of the mammalian neuropeptide processing protease PC2, and show that in contrast to vertebrate PC2, amontillado expression undergoes extensive regulation in the nervous system during development. In situ hybridization reveals that expression of amontillado is restricted to the final stages of embryogenesis when it is found in anterior sensory structures and in only 168 cells in the brain and ventral nerve cord. After larvae hatch from their egg shells, the sensory structures and most cells in the CNS turn off or substantially reduce amontillado expression, suggesting that amontillado plays a specific role late in embryogenesis. Larvae lacking the chromosomal region containing amontillado show no gross anatomical defects and respond to touch. However, such larvae show a greatly reduced frequency of a hatching behavior of wild- type Drosophila in which larvae swing their heads, scraping through the eggshell with their mouth hooks. Ubiquitous expression of amontillado can restore near wild-type levels of this behavior, whereas expression of amontillado with an alanine substitution for the catalytic histidine cannot. These results suggest that amontillado expression is regulated as part of a programmed modulation of neural signaling that controls hatching behavior by producing specific neuropeptides in particular neurons at an appropriate developmental time.}, author = {Siekhaus, Daria E and Fuller, Robert}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {16}, pages = {6942 -- 6954}, publisher = {Society for Neuroscience}, title = {{A role for amontillado the Drosophila homolog of the neuropeptide precursor processing protease PC2 in triggering hatching behavior}}, doi = {10.1523/jneurosci.19-16-06942.1999}, volume = {19}, year = {1999}, } @article{11679, abstract = {We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n }, we let T|L denote the minimal subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T * such that, for every i , T∗|L(Ti) is homeomorphic to T i . We present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n 2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes time O(N log3 n) and uses linear space. The previous best for this problem was a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n }), where b 0 is the number of batches which do not result in a new component. For our particular application, b0≤1 . If all edges are deleted, then the best previously known deterministic algorithm requires time O(mn−−√) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology.}, author = {Henzinger, Monika H and King, V. and Warnow, T.}, issn = {1432-0541}, journal = {Algorithmica}, keywords = {Algorithms, Data structures, Evolutionary biology, Theory of databases}, pages = {1--13}, publisher = {Springer Nature}, title = {{Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology}}, doi = {10.1007/pl00009268}, volume = {24}, year = {1999}, } @article{11687, abstract = {When using traditional search engines, users have to formulate queries to describe their information need. This paper discusses a different approach to Web searching where the input to the search process is not a set of query terms, but instead is the URL of a page, and the output is a set of related Web pages. A related Web page is one that addresses the same topic as the original page. For example, www.washingtonpost.com is a page related to www.nytimes.com, since both are online newspapers. We describe two algorithms to identify related Web pages. These algorithms use only the connectivity information in the Web (i.e., the links between pages) and not the content of pages or usage information. We have implemented both algorithms and measured their runtime performance. To evaluate the effectiveness of our algorithms, we performed a user study comparing our algorithms with Netscape's `What's Related' service (http://home.netscape.com/escapes/related/). Our study showed that the precision at 10 for our two algorithms are 73% better and 51% better than that of Netscape, despite the fact that Netscape uses both content and usage pattern information in addition to connectivity information.}, author = {Dean, Jeffrey and Henzinger, Monika H}, issn = {1389-1286}, journal = {Computer Networks}, keywords = {Search engines, Related pages, Searching paradigms}, number = {11-16}, pages = {1467--1479}, publisher = {Elsevier}, title = {{Finding related pages in the world wide Web}}, doi = {10.1016/s1389-1286(99)00022-5}, volume = {31}, year = {1999}, } @article{11688, abstract = {Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality of the pages in a search engine index. We provide a simple, effective algorithm for approximating the quality of an index by performing a random walk on the Web, and we use this methodology to compare the index quality of several major search engines.}, author = {Henzinger, Monika H and Heydon, Allan and Mitzenmacher, Michael and Najork, Marc}, issn = {1389-1286}, journal = {Computer Networks}, keywords = {Search engines, Index quality, Random walks, PageRank}, number = {11-16}, pages = {1291--1303}, publisher = {Elsevier}, title = {{Measuring index quality using random walks on the web}}, doi = {10.1016/s1389-1286(99)00016-x}, volume = {31}, year = {1999}, } @inproceedings{11691, abstract = {In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.}, author = {Goel, Ashish and Henzinger, Monika H and Plotkin, Serge and Tardos, Eva}, booktitle = {Proceedings of the 31st annual ACM symposium on Theory of computing}, issn = {0196-6774}, keywords = {Scheduling, Flow time}, location = { Atlanta, GA, United States}, pages = {189--197}, publisher = {Association for Computing Machinery}, title = {{Scheduling data transfers in a network and the set scheduling problem}}, doi = {10.1145/301250.301300}, year = {1999}, } @article{11769, abstract = {This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of Ω(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where the weights of the edges are between 1 and U.}, author = {Henzinger, Monika H and King, Valerie}, issn = {1557-735X}, journal = {Journal of the ACM}, number = {4}, pages = {502--516}, publisher = {Association for Computing Machinery}, title = {{Randomized fully dynamic graph algorithms with polylogarithmic time per operation}}, doi = {10.1145/320211.320215}, volume = {46}, year = {1999}, } @article{8526, author = {Kaloshin, Vadim}, issn = {0003-486X}, journal = {The Annals of Mathematics}, keywords = {Statistics, Probability and Uncertainty, Statistics and Probability}, number = {2}, pages = {729--741}, publisher = {JSTOR}, title = {{An extension of the Artin-Mazur theorem}}, doi = {10.2307/121093}, volume = {150}, year = {1999}, }