BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Peruvemba Sundaram Ravi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COData Structures and AlgorithmsDiscrete Mathematicsmath.OC

Catalog footprint

Research overview

3works
4topics
3close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

3 publications

preprint2026arXiv

On structural properties of some probable R(3,10)R(3, 10)-critical graphs

The Ramsey number R(s,t)R(s, t) is the smallest positive integer nn such that every graph on nn vertices contains either a clique of size ss or an independent set of size tt. An R(s,t)R(s,t)-critical graph is a graph on R(s,t)−1R(s,t)-1 vertices that contains neither a clique of size ss nor an independent set of size tt. It is known that 40≤R(3,10)≤4240\leq R(3, 10)\leq 42. We study the structure of a R(3,10)R(3,10)-critical graphs by assuming R(3,10)=42R(3, 10)=42. We show that if such a graph exists then its minimum degree and vertex connectivity are the same and is 6,76, 7 or 88. Then we find all the possible degree sequences of such graphs. Further, we show that if such a graph exists, then its diameter is either 22 or 33, and if it has diameter 22 and minimum degree 66, then it has only 2121 choices for its degree sequence.

Open access
preprint2015arXiv

Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture

Coffman and Sethi proposed a heuristic algorithm, called LD, for multi-processor scheduling, to minimize makespan over flowtime-optimal schedules. LD algorithm is a natural extension of a very well-known list scheduling algorithm, Longest Processing Time (LPT) list scheduling, to our bicriteria scheduling problem. Moreover, in 1976, Coffman and Sethi conjectured that LD algorithm has precisely the following worst-case performance bound: 54−34(4m−1)\frac{5}{4} - \frac{3}{4(4m-1)}, where m is the number of machines. In this paper, utilizing some recent work by the authors and Huang, from 2013, which exposed some very strong combinatorial properties of various presumed minimal counterexamples to the conjecture, we provide a proof of this conjecture. The problem and the LD algorithm have connections to other fundamental problems (such as the assembly line-balancing problem) and to other algorithms.

Open access
preprint2013arXiv

Worst-Case Performance Analysis of Some Approximation Algorithms for Minimizing Makespan and Flow-Time

In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules, called LD algorithm, has a simple worst-case performance bound: (5m-2)/(4m-1), where m is the number of machines. We study structure of potential minimal counterexamples to this conjecture and prove that the conjecture holds for the cases (i) n > 5m, (ii) m = 2, (iii) m = 3, and (iv) m greater than or equal to 4, n less than or equal to 3m, where n is the number of jobs. We further conclude that to verify the conjecture, it suffices to analyze the following case: for every m greater than or equal to 4, n is either equal to 4m or 5m.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.