Computer Science and Engineering: Recent submissions
Now showing items 1-30 of 89
-
Planar graph coloring is not self-reducible, assuming P ≠ NP
(1991)We show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of our result is that the ... -
Finding nonfaulty subtrees in faulty binary tree architectures
(1994)In this paper we have studied fault tolerance of a full binary tree in terms of availability of non-faulty (full) subtrees. When an unaugmented full binary tree is faulty, then the computation can be carried out on the ... -
Improved bounds for the max-flow min-multicut ratio for planar and Kr, r-free graphs
(1993)We consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this ... -
On-line algorithms for weighted bipartite matching and stable marriages
(1994)We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This algorithm is optimal - there ... -
Modeling of free-form surfaces and shape from shading
(2004)Modeling a free-form 3D-surface from a single view has been a widely pursued problem. The existing schemes are either fully-automatic shape-from-X techniques or involve adept interaction from the user but little or no ... -
Synthesis of application specific multiprocessor architectures for process networks
(2004)In this paper, we address the problem of synthesis of application specific multiprocessor SoC architectures for process networks of streaming applications. An application is modeled as Kahn Process Network (KPN) which makes ... -
A Trimaran based framework for exploring the design space of VLIW ASIPs with coarse grain functional units
(2002)It is widely accepted that use of an Application Specific Instruction Set Processor (ASIP) in an embedded system can provide a solution which is much more flexible than ASICs and much more efficient than standard processors ... -
Low-complexity fuzzy relational clustering algorithms for Web mining
(2001)This paper presents new algorithms-fuzzy c-medoids (FCMdd) and robust fuzzy c-medoids (RFCMdd)-for fuzzy clustering of relational data. The objective functions are based on selecting c representative objects (medoids) from ... -
Speeding up program execution using reconfigurable hardware and a hardware function library
(1998)This paper describes a co-design environment which follows a new approach for speeding up compute intensive applications. The environment consists of three major components. First, a target architecture consisting of a ... -
TCP k-SACK: a simple protocol to improve performance over lossy links
(2001)We propose k-SACK, a TCP variant that has considerably improved throughput characteristics over lossy links. A k-SACK source does not consider every packet loss as an indication of congestion. It uses the selective ... -
Evaluation of various routing architectures for multi-FPGA boards
(2000)Multi-FPGA boards are being used for logic emulation, rapid prototyping, custom computing and low volume subsystem implementation. A key feature which characterizes these boards is their routing architecture (RA). Inter-FPGA ... -
Faster and simpler algorithms for multicommodity flow and other fractional packing problems
(1998)This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach to these problems which yields faster ... -
A complexity effective communication model for behavioral modeling of signal processing applications
(2003)In this paper, we argue that the address space of memory regions that participate in inter task communication is over-specified by the traditional communication models used in behavioral modeling, resulting in sub-optimal ... -
SoC synthesis with automatic hardware-software interface generation
(2003)Design of efficient system-on-chips (SoCs) requires thorough application analysis to identify various compute intensive parts. These compute intensive parts can be mapped to hardware in order to meet the cost as well as ... -
An analytical framework for path reliabilities in mobile ad hoc networks
(2003)An ad hoc network is a collection of mobile nodes connected through multi-hop wireless links without the required intervention of any centralized access point or existing infrastructure. In this work, we have developed an ... -
Exploring storage organization in ASIP synthesis
(2003)Performance estimation which drives the design space exploration is usually done by simulation. With increasing dimensions of the design space, simulator based approaches become too time consuming. In the domain of application ... -
An architectural framework to deploy scatternet-based applications over Bluetooth
(2003)Bluetooth is a promising wireless personal area network technology and is on the verge of being ubiquitously deployed over a wide range of devices. The basic unit of a Bluetooth network is a centralized master-slave topology, ... -
Dynamic access control framework based on events: a demonstration
(2003)Access control policies in the e-commerce domain can be quite complex, affecting the response time provided to the users. We describe an event-based access control system that can potentially reduce the customer response ... -
An energy-conscious algorithm for memory port allocation
(2002)Multiport memories are extensively used in modern system designs because of the performance advantages they offer. The increased memory access throughput could lead to significantly faster schedules in behavioral synthesis. ... -
A new performance evaluation approach for system level design space exploration
(2002)Application specific systems have potential for customization of design with a view to achieve a better cost-performance-power trade-off. Such customization requires extensive design space exploration. In this paper, we ... -
The capacity of multi-hop wireless networks with TCP regulated traffic
(2002)We study the dependence of the capacity of multi-hop wireless networks on the transmission range of nodes in the network with TCP regulated traffic. Specifically, we examine the sensitivity of the capacity to the speed of ... -
QoS based scheduling for incorporating variable rate coded voice in Bluetooth
(2001)Bluetooth is an emerging standard low-cost indoor pico-cellular wireless systems. It is a master driven time division duplex (TDD) system. Real time services such as voice are given 64 kbps bandwidth in Bluetooth. However ... -
Evaluating register file size in ASIP design
(2001)Interest in synthesis of Application Specific Instruction Set Processors or ASIPs has increased considerably and a number of methodologies have been proposed for ASIP design. A key step in ASIP synthesis involves deciding ... -
ASIP design methodologies: survey and issues
(2001)Interest in synthesis of Application Specific Instruction Processors or ASIPs has increased considerably and a number of methodologies have been proposed in the last decade. This paper attempts to survey the state of the ... -
Improved multicast routing with delay and delay variation constraints
(2000)Multi point routing algorithms capable of satisfying quality of service constraints such as delay boundedness and delay variation boundedness are becoming crucial with the advent of high speed networks. This paper addresses ... -
Smart proxy: reducing latency for HTTP based Web transfers across satellite links
(2000)Hypertext Transfer Protocol (HTTP), the prevalent application layer protocol in the Internet has had a major role in the widespread and easy access to the Internet. With the increasing amount of data transfer over the ... -
A new divide and conquer method for achieving high speed division in hardware
(2002)Presents a new method of performing division in hardware and explores different ways of implementing it. This method involves computing a preliminary estimate of the quotient by splitting the dividend, performing division ... -
Energy efficiency and throughput for TCP traffic in multi-hop wireless networks
(2002)We study the performance metrics associated with TCP-regulated traffic in multi-hop wireless networks that use a common physical channel (e.g., IEEE 802.11). In contrast to earlier analyses, we focus simultaneously on two ... -
Hybrid Multi-FPGA board evaluation by limiting multi-hop routing
(2002)Multi-FPGA Boards (MFBs) have been in use for more than a decade for emulation of the digital circuits in many applications. Key feature of an MFB architecture is its inter-FPGA connections. There are two types of inter-FPGA ... -
A simulation study of multi-hop wireless network
(2002)Over a period of time there has been a massive revolution in wireless devices, ranging from centralized to infrastructureless ad hoc networks. The routing layer in an ad hoc network des the network into a seamless entity ...