Publications

Updated December 22, 2016.

Convex Visibility

  • S. Biswas, D. C. Prasad and S. P. Pal,
    Recognizing weakly convex visible
    polygons, Computational Geometry: Theory and Applications,
    Elsevier, North-Holland, 10 (1998), pp. 171-186.

  • S. K. Ghosh,
    A. Maheshwari, S. P.Pal and C. E. Veni Madhavan,
    An algorithm for recognizing palm polygons,
    The Visual Computer: Special issue on Computational
    Geometry (Invited paper), 10 (1994), pp. 443-451, Springer-Verlag.

  • S. Biswas, D. C. Prasad and S. P. Pal, Algorithms for convex
    visibility problems, Proceedings of the fourteenth conference on
    Foundations of Software Technology and Theoretical Computer Science,
    New Delhi, India, Lecture Notes in Computer Science, vol. 880,
    pp. 181-192, 1994, Springer-Verlag.

  • S. K. Ghosh, A. Maheshwari, S. P.Pal and C. E. Veni Madhavan,
    An algorithm for recognizing palm polygons,
    Proceedings of the Second Canadian Conference on
    Computational Geometry, pp. 246-251, August 1990.

Channel Routing

  • R. K. Pal (Ph. D. 1991-1993), S. P. Pal and A. Pal,
    An algorithm for finding a non-trivial
    lower bound for channel
    routing, INTEGRATION: The VLSI Journal,  25 (1998), pp. 71-84, Elsevier, North-Holland.
     

    Abstract

    Channel routing is a key problem in the physical design of VLSI chips. It is known that max(dmax, vmax) is a lower bound on the number of tracks required in the reserved two-layer Manhattan routing model, where dmax is the channel density and vmax is the length of the longest path in the vertical constraint graph. In this paper we propose a deterministic polynomial time algorithm that computes a better and non-trivial lower bound on the number of tracks required for routing a channel without doglegging. This algorithm is also applicable for computing a lower bound on the number of tracks in the three-layer no-dogleg HVH routing as well as two- and three-layer restricted dogleg routing models.

    Keywords: Channel routing problem; Channel constraint graphs; Reserved layer Manhattan routing model; Doglegging; Lower bound.

    -----------------------------------------------------------------------------------

  • R. K. Pal, S. P. Pal and A. Pal, A general graph theoretic framework
    for multi-layer channnel routing,
    Proceedings of the Eighth International IEEE
    Conference on VLSI Design, pp. 202-207, Delhi, Jan 1995.

  • R. K. Pal, S. P. Pal and A. Pal, Computing area and wire length
    efficient routes for channels, Proceedings of the Eighth International IEEE
    Conference on VLSI Design, pp. 196-201, Delhi, Jan 1995.
     

  • R. K. Pal, S. P. Pal and A. Pal, Absolute approximation for
    channel routing is NP-hard, Proceedings of the Fourth National
    Seminar on Theoretical Computer Science, IIT Kanpur, pp. 28-41, 1994.
     

  • R. K. Pal, S. P. Pal, and A. Pal, Minimizing net wire length in
    multi-layer channel routing, Proceedings of the Silver Jubilee Workshop
    on Computing and Intelligent Systems (Invited paper), pp. 171-188,
    Indian Institute of Science, Bangalore, Dec 1993.
     

  • R.K. Pal, S. P. Pal, and A. Pal, On the computational complexity of
    area and wire length minimization in multi-layer
    channel routing, Proceedings of the Third National
    Seminar on Theoretical Computer Science, pp. 103-119, IIT Kharagpur, June 1993.

  • R.K. Pal, S. P. Pal, A. K. Datta and A. Pal, NP-completeness of multi-layer
    no-dogleg channel routing and an efficient heuristic, Proceedings of the
    Fourth International Conference on VLSI Design, pp. 80-83, January 1993.

Others

Internet modelling and simulation, Distributed computing

  • Smruti Sarangi (B. Tech. 1998-2002), P. N. Sireesh (B. Tech. 1998-2002) and S. P. Pal,
    A Scalable, Efficient and General Monte Carlo Scheme for Generating Synthetic Web Request Streams,
    International Journal of Computer Systems Science and Engineering, CRL Publishing Ltd., UK, Vol. 18, no. 3, pp. 121-128, May 2003.

    ABSTRACT: We propose a Monte Carlo scheme (GRAPES) for generating synthetic web request streams. These request streams obey the Zipf page popularity distribution and temporal locality in the form of log-normal stack-distance distribution. Our algorithm avoids the use of an explicit stack; it uses a precomputed set of coefficients representing stack-distance distribution to generate web page requests. Using these coefficients our the algorithm runs in time proportional to the number of generated requests in contrast to other request stream generators that run in time proportional to the product of the stack size and the number of generated requests. The performance plots suggest a speedup of an order of magnitude for large inputs. We use an intricate randomization strategy to produce a uniform and random request stream. Our scheme is amenable to an efficient parallel implementation.

    -------------------------------------------------------------------------------

  • Smruti Sarangi (B. Tech. 1998-2002), P. N. Sireesh (B. Tech. 1998-2002) and S. P. Pal,
    Generating synthetic web request streams,
    Technical Report, TR/IIT/CSE/SPP3, Nov 2001, Department of Computer Science and Engineering, IIT Kharagpur, 721302, India,

  • Enhancing the performance of a mesh of caches by appropriately distributing cache, Joydeep Chandra (M. Tech. CSE Jan 2002), S. P. Pal, Rajiv Ranjan Suman (M. Tech. CSE Jan 2003), G. Sudha Anil Kumar (M. Tech (Integrated) 1999-2004) and Dilip Sarkar (Univ. of Miami), a previous version is documented as Technical Rport No. IIT/TR/CSE/SPP1/2003, Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, 721302, India, May 2003 (submitted for publication).

  • Virtual video caching: A scalable and generic technique for improved quality of video service, S. P. Pal, R. R. Suman, G. S. Anil Kumar and R. Malhotra, Proc. of the 2nd Trusted Internet Workshop, HiPC 2003, Hyderabad, India, December 17, 2003 (Journal of High Speed Networks, vol. 13, no. 4, 2004, IOS Press).

  • Fair leader election by randomized voting, Siddhartha Brahma (B. Tech. CSE, 2001-2005), Sandeep Macharla (M. Tech. CSE 2004), S. P. Pal and Sudhir Kumar Singh (M. Sc. Maths. and Computing, 2004), presented in the 1st International Conference on Distributed Computing and Internet Technology, Bhubaneshwar, India, Dec. 2004.

Graphs and hypergraphs

  • Niranjan Balachandran, Rogers Mathew, Tapas Kumar Mishra, Sudebkumar Prasant Pal:
    Bisecting and D-secting families for set systems. Discrete Applied Mathematics (Elsevier) (2017), now online. https://doi.org/10.1016/j.dam.2017.05.005

  • Tapas Kumar Mishra, Sudebkumar Prasant Pal:
    Strong (r,p) Cover for Hypergraphs. CoRR abs/1507.03160 (2015)

  • Tapas Kumar Mishra, Sudebkumar Prasant Pal:
    An extremal problem in proper (r,p)-coloring of hypergraphs. CoRR abs/1507.02463(2015)

  • Tapas Kumar Mishra, Sudebkumar Prasant Pal:
    Bicoloring covers for graphs and hypergraphs. CoRR abs/1501.00343 (2015) 2014

  • Tapas Mishra and S. P. Pal ,
    Lower bounds for Ramsey numbers for complete bipartite and 3-uniform tripartite subgraphs, accepted for presentation in the Seventh Workshop on Algorithms and Computation, February 14-16, 2013, to be held in IIT Kharagpur, India (S. K. Ghosh and T. Tokuyama (Eds.): WALCOM 2013, LNCS 7748, pp. 257-264, 2013), full improved version in Journal of Graph Algorithms and Applications (special issue for WALCOM 2013), vol. 17, no. 6, pp. 671-688 (2013).

  • S. P. Pal,
    Coding, counting, cutset incomparability and coloring of labelled graphs and hypergraphs, In "Graph Theory: Research Directions", Editors: Pratima Panigrahi and S. B. Rao, Narosa Publishing House, February 2011, ISBN: 978-81-7319-997-4.

  • S. Shannigrahi (TIFR Mumbai) and S. P. Pal,
    Efficient Pruffer-like coding and counting labelled hypertrees, Proceedings of the International Symposium on Algorithms and Computation, ISAAC 2006, LNCS 4288, revised version in special issue of Algorithmica, vol. 54, pp. 208-225, Springer, 2009.

  • Nitin Kumar (M. Tech. 2008), Rahul Gokhale (M. Tech. CSE 2007), S. P. Pal and Mridul Aanjaneya (B. Tech (Hons.) 2008),
    Efficient protocols for contextual hypergraph bicoloring games, manuscript, July 2007.

Exact and robust computing

  • S. P. Pal, Rakesh Kumar Koul (M. S. 1998-2000), Frahad Musadeekh, P. H. D. Ramakrishna (M. Tech. CSE 1998-2000) and Hironmay Basu (B. Tech. CSE 1999-2003)
    Computations that require higher than double precision for robust and exact decision making, International Journal of Computer Mathematics, vol. 81, no. 5, pp. 595-605, May 2004.

  • Frahad Musadeekh and S. P. Pal,
    Using very small error bounds for exactly computing signs of expressions,
    Proc. of the National Conference on Mathematical and Computational Models, December 27-28, 2001, PSG College of Technology, Coimbatore, Tamil Nadu, India.

  • P. H. D. Ramakrishna (M. Tech. 1998-2000), Sudebkumar Prasant Pal, Samir Bhalla (M. Tech. 2001-2003), Hironmay Basu (B. Tech. 1999-2003) and Sudhir Kumar Singh (M. Sc. Maths and Computing, 1999-2004),
    Computing sharp and scalable bounds on errors in approximate zeros of univariate polynomials (click here to download from http://arXiv.org),
    Proceedings of the International Conference on Analysis and Discrete Structures, December 2002 (ICADS 2002).

  • Siddhartha Brahma (B Tech CSE 2001-2005), P. H. D. Ramakrishna (M Tech CSE 1998-2000) and S. P. Pal, A new and novel method for computing an upper bound on the distance of an approximate zero from an exact zero of a univariate polynomial, International Journal of Computer Mathematics, vol. 81, no. 12, pp. 1549-1557, December 2004.