NDLI: Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem

Please wait, while we are loading the content...

Editorial message: special track on artificial intelligence and computional logic

Editorial message: special track on agents, interactions, mobility, and systems (AIMS)

Editorial message: bioinformatics track

Editorial message: special track on computational sciences

Computer applications in health care

Editorial message special track on computer security

Editorial message: special track on coordination models, languages and applications

ACM SAC 2003: data mining track editorial

Database technology: track chair message

Editorial message: special track on digital contents for education

Editorial message: special track on E-commerce technologies

Editorial message for the special track on embedded systems: applications, solutions, and techniques

Editorial message: special track on evolutionary computation and optimization SAC 2003

Editorial message: special track on image and video databases

Editorial message: special track on information access and retrieval

Editorial message: special track on mobile computing and applications

Message from multimedia and visualization track organizers

Editorial message: special track on parallel and distributed systems and networking

Editorial message: special track on the programming languages and object technologies

Editorial message: special track on software engineering: applications, practices and tools

Editorial message: special track on Web technologies and applications

A coarse-grain parallel genetic algorithm for finding Ramsey Numbers

Stability vs optimality tradeoff in game theoretic mechanisms for QoS provision

A recursive connectionist approach for predicting disulfide connectivity in proteins

Towards differentiation-enabled Fortran 95 compiler technology

Introducing lateral thinking in search engines with interactive evolutionary algorithms

Authentication of LZ-77 compressed data

Coordination-based distributed constraint solving in DICE

Tough constraint-based frequent closed itemsets mining

PINE: Podium Incremental Neighbor Evaluator for classifying spatial data

An approach for adaptable learning systems with respect to psychological aspects

Semantic matchmaking in a P-2-P electronic marketplace

Partitioning of embedded applications onto heterogeneous multiprocessor architectures

Multi-objective optimization in area coverage problems for cellular communication networks: evaluation of an elitist evolutionary strategy

Image retrieval with embedded region relationships

Supervised term weighting for automated text categorization

Adaptive dissemination of dynamic information services in an extended data broadcast environment

Cluster rendering of skewed datasets via visualization

Performance prediction of wormhole switching in hypercubes with bursty traffic pattern

Features of the concurrent programming language Aldwych

An integrated framework for formal development of open distributed systems

Constructing Web search queries from the user's information need expressed in a natural language

Implementing Fuzzy Expert System for intelligent buildings

A multi-agent system for remote psychological profiling with role playing games based tests

A Markov Random Field model of microarray gridding

Automatic parallelism in differentiation of Fourier transforms

Enhancement of wavelet-based medical image retrieval through feature evaluation using an information gain measure

Authentication and access delegation with user-released certificates

Basic components for constraint solver cooperations

Bootstrapping a data mining intrusion detection system

Integrated querying of XML data in RDBMSs

Evaluating the usability of portable electronic books

A multi-agent system for e-barter including transaction and shipping costs

A software framework for efficient system-level performance evaluation of embedded systems

Multi-heuristic list scheduling genetic algorithm for task scheduling

An adaptive three-dimensional DCT compression based on motion analysis

Email classification for contact centers

Selecting the best valid scopes for wireless dissemination of location-dependent data

Hierarchical video indexing based on changes of camera and object motions

BluePoint: a bluetooth-based architecture for location-positioning services

A transition-based strategy for object-oriented software testing

Modeling the meaning of transitions from and to concurrent states in UML state machines

Design and implementation of a graphical interface to XQuery

Schedulers for rule-based constraint programming

Are multiagent algorithms relevant for real hardware?: a case study of distributed constraint algorithms

Gene functional classification by semi-supervised learning from heterogeneous data

Dynamic solver selection for an Internet simulation backbone

On the fuzzy Bayesian inference of population annoyance level caused by noise exposure

Delay-based circuit authentication and applications

A new approach to scalable Linda-systems based on swarms

Mining maximal frequent intervals

Accessee controlled type selection for a multiple-type object

Architecture to support dynamic composition of math lesson plans

A model for the configurable composition and synchronization of complex trading activities

A methodology for the efficient architectural exploration of energy-delay trade-offs for embedded systems

A spanning-tree-based genetic algorithm for some instances of the rectilinear Steiner problem with obstacles

Automatic interpretation of soccer video for highlights extraction and annotation

Expanding domain-specific lexicons by term categorization

Broadcast program generation for unordered queries with data replication

Visualization of association rules over relational DBMSs

An improvement on binary-swap compositing for sort-last parallel rendering

Can a parser be generated from examples?

Representing the applications and compositions of design patterns in UML

Views for light-weight Web ontologies

Image texture classification using datagrams and characteristic views

A top down approach for MAS protocol descriptions

Terminology-driven mining of biomedical literature

Cl_matcont: a continuation toolbox in Matlab

Modeling the workflow of prescription writing

An approach to secure information flow on Object Oriented Role-based Access Control model

PeerSpaces: data-driven coordination in peer-to-peer networks

A new distributed data mining model based on similarity

Hybrid log segmentation for assured damage assessment

InterMediActor: an environment for instructional content design based on competences

Organizational modeling in UML and XML in the context of workflow systems

ARCHITECT-R: a system for reconfigurable robots design

A hybrid AI approach for nurse rostering problem

Improving image retrieval effectiveness in query-by-example environment

Multiclass text categorization for automated survey coding

Cost efficient broadcast based cache invalidation for mobile environments

Self-manifestation of composite multimedia objects to satisfy security constraints

Automatic code generation for a convection scheme

Pointer analysis of multithreaded Java programs

On the composition of Java frameworks control-flows

Ontology-focused crawling of Web documents

Designing and specifying mobility within the multiagent systems engineering methodology

FPV: fast protein visualization using Java 3D™

Nonlinear instability in multiple time stepping molecular dynamics

Echo-cardiography on the Web: design and set-up of a virtual community of experts

A fast and effective steganalytic technique against JSteg-like algorithms

Eliciting coordination policies from requirements

Optimization of a language for data mining

Distributed query adaptation and its trade-offs

Architecture for user-controlled e-privacy

Validation of code-improving transformations for embeded systems

Automatic test program generation for pipelined processors

An architecture to support distributed data retrieval in specialized formats

Combining state and model-based approaches for mobile agent load balancing

Overlay multicast for video on demand on the Internet

An alternative routing algorithm for the pyramid structures

A method for the automatic generation of test suites from object models

An XML-based conversational protocol for Web services

Enabling mobile agents to dynamically assume roles

Pathways database system: an integrated set of tools for biological pathways

A treecode algorithm for computing Ewald summation of dipolar systems

Integrating smart card access to Web-based medical information systems

Availability of protocol goals

Comparing semantic frameworks for coordination: on the conformance issue for coordination media

Building knowledge discovery into a geo-spatial decision support system

XQuery speedup using replication in mapping XML into relations

Addressing E-business privacy concerns: the roles of trust and value compatibility

An optimized Java interpreter for connected devices and embedded systems

Manpower scheduling with time windows

Methods for ranking information retrieval systems without relevance judgments

Mobile agent based pervasive systems manager for enterprise network

Estimation of 3D shape and reflectance using multiple moiré images and shading model

A simple and energy-efficient routing protocol for radio networks

Towards model-based generation of self-priming and self-checking conformance tests for interactive systems

Classification of ad-hoc multi-lateral collaborations based on local workflow models

Managing agent life cycles in open distributed systems

Labrat LIMS: an extensible framework for developing laboratory information management, analysis, and bioinformatics solutions for microarrays

Long time step molecular dynamics using targeted Langevin stabilization

Role-based authorization in decentralized health care environments

Authenticity in a reliable protocol for mobile computing

An extensible architecture-based framework for coordination languages

Discovering interesting information in XML data with association rules

Applying genetic algorithms in database partitioning

reality: a scalable intelligent travel planner

TinyGALS: a programming model for event-driven embedded systems

Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem

Evaluating database selection algorithms for distributed search

UbiData: ubiquitous mobile file service

A framework of individually-focused teleconferencing (IFT) via an efficient 3D reprojection technique

An optimal broadcasting schema for multidimensional mesh structures

Using operational distributions to judge testing progress

Agent-based services for information portals

Similar_Join: extending DBMS with a bio-specific operator

Quantification of trabecular bone mass and orientation using Gabor wavelets

Intelligent agents for patient monitoring and diagnostics

A role administration system in role-based authorization infrastructures: design and implementation

Synchronization analysis for decentralizing composite Web services

An efficient method for mining associated service patterns in mobile web environments

A dynamic data/currency protocol for mobile database design and reconfiguration

Systems architecture for pervasive retail

An efficient time representation for real-time embedded systems

On the influence of GVR in vehicle routing

Disproving the fusion hypothesis: an analysis of data fusion via effective information retrieval strategies

Extended Internet caching protocol: a foundation for building ubiquitous Web caching

A new cache management algorithm for multimedia storage systems

A lightweight Java taskspaces framework for scientific computing on computational grids

On the use of the classification-tree method by beginning software testers

WebSOGO: a global ontology for describing Web sources

Integrative approach for computationally inferring protein domain interactions

Discretizing aerosol dynamics with B-splines

SOM: feature extraction from patient discharge summaries

A protection scheme for collaborative environments

Using latent semantic indexing to filter spam

COSAR: commitment-oriented "sense and respond" system for microelectronic manufacturing

Using agents for multi-target search on the Web

Interactive computation and visualization of fetch using standard computer graphics hardware

A dynamic load distribution strategy for systems under high task variation and heavy traffic

Property-oriented testing: a strategy for exploring dangerous scenarios

RepWeb: replicated Web with referential integrity

A component-based implementation of multiple sequence alignment

Real-time monitoring of large scientific simulations

Applying information visualization techniques to capture and explore the course of cognitive behavioral therapy

Access-controlled resource discovery for pervasive networks

The bitmap-based feature selection method

iGrocer: a ubiquitous and pervasive smart grocery shopping system

An indexing model of HTML documents

Supporting real-time visualization with the HDoV tree

Implementation of a proactive load sharing scheme

An initial investigation of test driven development in industry

Similarity-based clustering of Web transactions

Identify amino acid candidates critical for function of rat imidase by cross-reference voting in imidase superfamily

Hybrid (OpenMP and MPI) parallelization of MFIX: a multiphase CFD code for modeling fluidized beds

Data visualization using kernel density estimation to examine patterns of physician practice

Network traffic anomaly detection based on packet bytes

A density based aapproach to classification

CIGMA: aCtive Inventory service in Global e-MArket based on efficient catalog management

Web metasearch: rank vs. score based rank aggregation methods

Modeling and visualizing uncertainty in a global water balance model

A methodology to provide and use interchangeable services

Recognizing the relations between Web pages using artificial neural network

Inference of transcriptional regulation relationships from gene expression data

Terascale simulation of cumulus convection on ASCI WHITE

A unified security framework for networked applications

An efficient data structure for decision rules discovery

Efficient evaluation of relevance feedback for multidimensional all-pairs retrieval

Streaming of DivX AVI movies

Efficient mediators through dynamic code generation: a method and an experiment

Design time support for adaptive behavior in Web sites

Prototype-based mining of numeric data streams

A customizable hybrid approach to data clustering

ADMiRe: an algebraic approach to system performance analysis using data mining techniques

Mining confident co-location rules without a support threshold

Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem

Content Provider	ACM Digital Library
Author	Julstrom, Bryant A. Raidl, Günther R.
Abstract	Given a connected, weighted, undirected graph G and a bound D, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of lowest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 < D < n - 1, where n is the number of vertices in G. An existing greedy heuristic for the problem, called OTTC, is based on Prim's algorithm. OTTC usually yields poor results on instances in which the triangle inequality approximately holds; it always uses the lowest-weight edges that it can, but such edges do not in general connect the interior nodes of low-weight bounded-diameter trees. A new randomized greedy heuristic builds a bounded-diameter spanning tree from its center vertex or vertices. It chooses each next vertex at random but attaches the vertex with the lowest-weight eligible edge. This algorithm is faster than OTTC and yields substantially better solutions on Euclidean instances. An evolutionary algorithm encodes spanning trees as lists of their edges, augmented with their center vertices. It applies operators that maintain the diameter bound and always generate valid offspring trees. These operators are efficient, so the algorithm scales well to larger problem instances. On 25 Euclidean instances of up to 1000 vertices, the EA improved substantially on solutions found by the randomized greedy heuristic.
Starting Page	747
Ending Page	752
Page Count	6
File Format	PDF
ISBN	1581136242
DOI	10.1145/952532.952678
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-03-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Bounded-diameter spanning tree Greedy heuristics Randomized heuristics Local improvement Edge-list encoding
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in