Path Maximum Query and Path Maximum Sum Query in a Tree
スポンサーリンク
概要
- 論文の詳細を見る
Let T be a node-weighted tree with n nodes, and let π(u, v) denote the path between two nodes u and v in T. We address two problems: (i) Path Maximum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight on π(u, v) can be found quickly. (ii) Path Maximum Sum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight sum subpath of π(u, v) can be found quickly. For the problems we present solutions with O(1) query time and O(n log n) preprocessing time.
- （社）電子情報通信学会の論文
- 2009-02-01
著者
-
Kim Sung
Department Of Anatomy
-
Cho Jung-sik
Department Of Computer Science And Engineering Chung-ang University
-
Kim Sung
Chung‐ang Univ. Seoul Kor
-
KIM Soo-Cheol
Department of Computer Science and Engineering, Chung-Ang University
-
Kim Soo-cheol
Department Of Computer Science And Engineering Chung-ang University
関連論文
- Process development for mycelial growth and polysaccharide production in Tricholoma matsutake liquid culture(MICROBIAL PHYSIOLOGY AND BIOTECHNOLOGY)
- Different channel modulation in arterial smooth muscle cells of diabetes(Special lecture, 52^ Annual Meeting of the Japan Society of Smooth Muscle Research)
- Kaempferol Attenuates 2-Deoxy-D-ribose-Induced Oxidative Cell Damage in MC3T3-E1 Osteoblastic Cells(Biopharmacy)
- A Case of AV Reentrant Tachycardia due to a Concealed Accessory Pathway with Retrograde Conduction Manifested by Isoproterenol
- P-IS-44 Correlation of HLA-G gene Expression with Various Prognostic Factors in Ovarian Carcinoma(Oncology 12,Group 99,International Session)
- P-IS-41 Analysis of Chromosomal Changes in Serous Ovarian Carcinoma by Microarray Comparative Genomic Hybridization : Potential Predictive Markers for Chemoresistant Disease(Oncology 11,Group 98,International Session)
- Immunohistochemical analysis of p16INK4A protein overexpression in cervical intraepithelial neoplasia(Oncology 4)
- 2-8.Clinical Usefulness of Cervicogram as Primary Screening Test of Cervical Intraepithelial Neoplasia(Session 3 Oncology 3)
- Development and Industry of Health Functional Food in Korea
- A Screening Method for Estrogens Using an Array-Type DNA Glass Slide
- Clinicopathological significance of nuclear factor-kappa B, HIF-1 alpha, and vascular endothelial growth factor expression in stage III colorectal cancer
- Inhibition of Ca2+-Release–Activated Ca2+ Channel (CRAC) and K+ Channels by Curcumin in Jurkat-T Cells
- Efficient Indexing and Querying XML Data Using Element Type in a Dynamic Environment(Papers Selected from 2003 International Technical Conference on Circuits/Systems, Computers and Communications(ITC-CSCC 2003))
- Ginsenoside Rg1 Suppresses Hepatic Glucose Production via AMP-Activated Protein Kinase in HepG2 Cells
- Occurrence of Hippocampal Sclerosis : Is One Hemisphere or Gender More Vulnerable?
- Radiometric ages of metamorphic and plutonic rocks in South Korea
- A Study of a Regeneration Reaction for Desulfurization Sorbents Using Natural Manganese Ore
- A Cytogenetic Study of Korean Native Goat Bred in the Nuclear Power Plant using the Micronucleus Assay
- Supernova Remnants in the AKARI IRC Survey of the Large Magellanic Cloud
- Microstructural Evolution of Joint Interface between Eutectic 80Au-20Sn Solder and UBM
- Ischemic Injury-Specific Gene Expression in the Rat Spinal Cord Injury Model Using Hypoxia-Inducible System
- Incidence and Clinical Patterns of Polypoidal Choroidal Vasculopathy in Korean Patients
- White Light Emission from Blue InGaN LED with Fluorescent Conjugated Polymer Blends
- Temperature-Sensitive Sol-Gel Transition Behavior of Biodegradable Four-Arm Star-Shaped PEG-PLGA Block Copolymer Aqueous Solution
- Background Nonselective Cationic Current and the Resting Membrane Potential in Rabbit Aorta Endothelial Cells
- Relationship Between Global Cytosolic Ca^ Concentration and Ca^ activated K^+ Current in Rabbit Cerebral Arterial Myocyte
- Alteration of antioxidant enzymes at the mRNA level during short-term starvation of rockbream Oplegnathus fasciatus
- Hypoglycemic Effect of Intestinally Administered Monosaccharide-Modified Insulin Derivatives in Rats
- Three New Stereoisomers of Condensed Tannins from the Roots of Rosa multiflora
- Residual Stress Behavior of Polyimide Thin Films : Effect of Precursors
- 頚椎に発生した浸潤性脂肪腫の犬の1例(外科学)
- Prevalence of hepatitis B and C virus infection among adults in Korea
- Multiple Brain Calcification in Chronic Lead Poisoning
- Maximal safe dose of I-131 after failure of standard fixed dose therapy in patients with differentiated thyroid carcinoma
- Genetic analysis of the cardiac sodium channel gene SCN5A in Koreans with Brugada syndrome
- A High-Performance Polycrystalline Silicon Thin-Film Transistor Using Metal-Induced Crystallization with Ni Solution
- Mitochondrial myopathy caused by clevudine therapy in chronic hepatitis B patients
- Transient Impairment of Hippocampus-dependent Learning and Memory in Relatively Low-Dose of Acute Radiation Syndrome is Associated with Inhibition of Hippocampal Neurogenesis
- Apoptosis by pan-caspase inhibitors in lipopolysaccharideactivated macrophages
- The Properties of Carbachol-Activated Nonselective Cation Channels at the Single Channel Level in Guinea Pig Gastric Myocytes
- Influence of Extracellular Na^+ Removal on Cytosolic Ca^ Concentration in Smooth Muscle Cells of Rabbit Cerebral Artery
- Dual roles of phorbol 12, 13-dibutyrate in the regulation of guinea-pig gastric contraction
- Anti-obesity Effect of Dioscorea nipponica Makino with Lipase-inhibitory Activity in Rodents(Food & Nutrition Science)
- Preload Dependency of the Time Interval Between the Onset of Mitral Inflow and the Early Diastolic Annular Motion : A Hemodialysis-Related Preload Reduction Study
- Preparation of Highly Ordered Mesoporous TiO_2 Materials with Crystalline Framework from Different Mesostructured Silica Templates via Nanoreplication
- Synthesis of Conducting Mesoporous Materials Implanting Carbon Nanotubes inside Particles
- Carcinoma of the External Auditory Canal and Middle Ear : Staging and Management Dilemma
- Electrochemical Study on the Reduction Mechanism of Uranium Oxide in a LiCl-Li_2O Molten Salt
- Study on the Characteristics of the Ion Exchange of Zeolite 4A in a Molten LiCl System
- Neuroprotection and Enhancement of Learning and Memory by BF-7
- An Improved Approach to the Instantaneous IMEP Method for Piston-Ring Assembly Friction Force Measurement
- The Benefits of Supplementary Private Health Insurance for Healthcare Utilization and Survival among Stomach Cancer Patients
- Species-Difference of Cyclooxygenase-2 in the Hippocampus of Rodents
- Identification and Characterization of Antioxidants from Sophora flavescens(Pharmacognosy)
- Link-Adaptive MAC Protocol for Wireless Multicast
- EFFECT OF Cl INCORPORATION ON THE PERFORMANCE OF AMORPHOUS SILICON THIN FILM TRANSISTOR
- Involvement of Oxidized Peroxiredoxin-3 in Cadmium- and Ceramide-induced Apoptosis of Human Neuroblastoma Cells
- Stochastic Analysis of Gas-Liquid-Solid Flow in Three-Phase Circulating Fluidized Beds
- In vitro Release and in vivo Anti-tumor Efficacy of Doxorubicin from Biodegradable Temperature-sensitive Star-shaped PLGA-PEG Block Copolymer Hydrogel
- Photochemical Generation of Nitric Oxide from 3,4-Bis-2'-chlorophenylfuroxan
- CYP724B2 and CYP90B3 Function in the Early C-22 Hydroxylation Steps of Brassinosteroid Biosynthetic Pathway in Tomato
- Topical immunomodulators are effective for treatment of vitiligo
- Dielectric properties of MgB_2O_6 (B^=Nb, Ta, Sb) at microwave frequencies
- プラズマ応用技術におけるシミュレーション研究 5. Kinetic Simulation of Micro Plasmas
- FM-P10 Involvement of rpoE in starvation stress response of Lactobacillus fermentum MS79(Section VIII Fermentation and Microbial Technology)
- H109 ANALYSIS OF FORCED CONVECTION IN A TUBE WITH CIRCULAR-SECTORED FINS(Electronics cooling-2)
- Influence of hydration status in normal subjects : fractional analysis of parameters of Tc-99m DTPA and Tc-99m MAG_3 renography
- DP-010-1 HCC in living donor liver transplantation : Do we need further modifications with the Milan criteria?
- Laparoscopic versus open radical cystectomy for the management of bladder cancer : Mid-term oncological outcome
- Solids Behavior in Freeboard of FCC Regenerator
- Creolar bodies in asthmatic children
- One - Pot Formation of a Cyclobutane from the Double Photocycloaddition Reactions of 1, 4 - Diethynylbenzene to Some o - Quinones
- Photoaddition Reaction of 1,4-Diethynylbenzene to Tetramethyl-1,4-benzoquinone and Photochemical Transformation of the Photoadducts
- FM-P4 Beta-carotene production of recombinant Escherichia coli engineered with whole mevalonate pathway or non-mevalonate pathway in batch cultures at different temperatures and pH(Section VIII Fermentation and Microbial Technology)
- Prediction of high-grade squamous intraepithelial lesions using the modified Reid index
- A Multi-Code Biorthogonal Code Keying with Constant Amplitude Coding(Wireless Communication Technologies)
- Are Low Total Serum Antioxidant Status and Elevated Levels of C-Reactive Protein and Monocyte Chemotactic Protein-1 Associated With Cardiac Syndrome X?
- Effect of Scutellariae Radix Extract on the High Glucose-Induced Apoptosis in Cultured Vascular Endothelial Cells(Biopharmacy)
- Preparation of Tantalum Powder from Ta_2O_5 by an Electrochemical Reduction in an LiCl-Li_2O Molten Salt System
- SB-03-1(033) Application of K-R Creep Damage Model for Type 316LN and HT-9 Stainless Steels(Materials Performance in Nuclear Application 3)
- Mass Analysis of Persuccinated Derivatives of Neutral Oligosaccharides Using Matrix-Assisted Laser Desorption/Ionization Time-of -Flight Mass Spectrometry
- Effects of KCNQ1 Channel Blocker, 293B, on the Acetylcholine-Induced Cl^- Secretion of Rat Pancreatic Acini
- C303 ENCLOSED CONVECTION WITH INTERNAL HEAT GENERATION UNDER OSCILLATING BOUNDARY WALL(Mixed convection)
- Cerebral cortical phospholipase A_2 activity of senescence-accelerated mouse is increased in an age-dependent manner
- H301 EXPERIMENTAL AND NUMERICAL ANALYSIS OF HEAT TRANSFER PHENOMENA IN A SENSOR TUBE OF A MASS FLOW CONTROLLER(Thermal problems in various systems)
- Numerical and Experimental Study for Falling Film in Ammonia Absorption Refrigeration Systems
- Mathematical Modeling and Simulation for Marangoni Convection by Surfactants in Liquid Falling Film
- Influence of thyroid-stimulating hormone on ^F-fluorodeoxyglucose and ^Tc-methoxyisobutylisonitrile uptake in human poorly differentiated thyroid cancer cells in vitro
- Submillimeter-scale Graphene Patterning through Ink-jet Printing of Graphene Oxide Ink
- Immunohistochemical Detection of Tyrosine Hydroxylase and Concentrations of Monoamines in the Substantia Nigra and Hypothalamus of Hereditary Microphthalmic Rats
- The Long -Term Effects of Complex Decongestive Physical Therapy on Lower Extremity Secondary Lymphedema and Quality of Life
- Two cases of pulmonary paragonimiasis on FDG-PET CT imaging
- The clinical value of dacryoscintigraphy in the selection of surgical approach for patients with functional lacrimal duct obstruction
- An in vitro Comparison of the Accuracy of Seven Electronic Apex Locators in Canals with Blood
- Chemical Investigation on the Mixture of Calcium hydroxide and Chlorhexidine digluconate
- Effects of Domain Size on Physical Properties of a Thermotropic Liquid Crystalline Polyester
- Sputtering Pressure Effects on Magnetization Reversal Mechanism and Magnetic Switching Volumes of CoSmICr Films
- Effects of AG490 on Lens Epithelial Cell Death Induced by H_2O_2
- Environmental Management System for Rural Region : Case Study at Atsumi District, Central Japan
- Path Maximum Query and Path Maximum Sum Query in a Tree