Ph.D. Thesis

• H. Narayanan: Theory of Matroids and Network Analysis Ph.D. Thesis, Department of Electrical Engineering, Indian Institute of Technology, Bombay, February 1974.

Book

• H. Narayanan: Submodular Functions and Electrical Networks. Annals of Discrete Mathematics 54 North Holland (London, New York, Amsterdam) (1997).
   

Selected Research Papers

• Journal Publications

In circuits the theme is essentially Network Theory Without Devices (NTWD). Also included are applications of Implicit Duality Theorem (IDT). In submodular functions the papers are essentially those related to Principal Partition and Principal Lattice of Partitions.

• H. Narayanan and M.N. Vartak, An elementary approach to the principal partition of a matroid, Transactions of the Institute of Electronics and Communication Engineers of Japan E64 (1981) 227-234.
• H. Narayanan, On the equivalence of Minty's painting theorem and Tellegen's theorem, International Journal of Circuit Theory and its Applications 13 (1985) 353-357 (NTWD)
• H. Narayanan, On the decomposition of vector spaces, Linear algebra and its applications 76 (1986) 61-98  (NTWD) (IDT)
• H. Narayanan, A unified construction of adjoint systems and networks, International Journal of Circuit Theory and its Applications 14 (1986) 263-276 (IDT)
• H. Narayanan, Topological transformations of electrical networks, International Journal of Circuit Theory and its Applications 15 (1987) 211-233 (NTWD)(IDT)
• H. Narayanan, On the minimum hybrid rank of a graph relative to a partition of its edges and its apppliction to electrical network analysis, International Journal of Circuit Theory and its Applications 18 (1990) 269-288 (NTWD)
• H. Narayanan, The principal lattice of partitions of a submodular function, Linear Algebra and its Applications 144 (1991) 179-216
• H. Narayanan, H. Saran and V.V. Vazirani, Randomized parallel algorithms for matroid union and intersection with applications to arborescences and edge disjoint spanning trees, SIAM Journal of Comput. 23 (1994) 387-397
• H. Narayanan, A rounding technique for the polymatroid membership problem, Linear Algebra and its Applications 221 (1995) 41-57
• H. Narayanan, Convolution and Dilworth truncation of submodular functions, Special Issue on Decision Sciences, Journal of Indian Institute of Science, Bangalore 75 (1995) 25-47
• H. Narayanan, S. Roy and S. Patkar, Approximation algorithms for min-k-overlap using the PLP approach, Journal of Algorithms 21 (1996) 306-330
• Sachin B. Patkar and H. Narayanan, A note on optimal covering augmentation for graphic polymatroids, Information Processing Letters, 79 (6) (2001) 285-290 (postscript)
• H. Narayanan, Some applications of an Implicit Duality Theorem to connections of structures of special types including Dirac and reciprocal structures, Systems & Control Letters 45 (2) (2002) 87-95 (IDT) (postscript)
• H.K.Pillai and H.Narayanan, On duality of behavioural systems, Multidimensional Systems and Signal Processing, 49 (6) (2002) 357-383. (postscript)
•  M.P.Desai,H. Narayanan,S.Patkar, The Realization of Finite State Machines by Decomposition and the Principal Lattice of Partitions of a Submodular Function,
  Special Issue on Submodular Functions, Discrete Applied Maths, 131, 2003, pp 299-310.
• S.Patkar and H.Narayanan,Fast On-line/Off-line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition, Journal of Combinatorial Optimization 7 (2003) 45-68.
• S.Patkar and H. Narayanan, Improving Graph Partitions using Submodular Functions,
  Special Issue on Submodular Functions, Discrete Applied Maths 131, 2003.( postscript)
• H. Narayanan, Minimization of Symmetric and General Submodular Functions,
  Special Issue on Submodular Functions, Discrete Applied Maths 131, 2003, pp 513-522.

•  
  Conference Publications

  The first paper is included because the general purpose circuit simulator BITSIM ( built at VLSI Design centre, IIT Bombay in 1992) which used efficient, sparse hybrid equation formulation, was based on it. The remaining are largely on partitioning and applications. The theory papers are based on Principal Lattice of Partitions and Principal Partition of a submodular function.

  • H. Narayanan, A theorem on graphs and its application to network analysis, Proceedings of IEEE International Symposium on Circuits and Systems (1979) 1008-1011

  • S. Roy and H. Narayanan, A new approach to the problem of PLA partitioning using the theory of the principal lattice of partitions of a submodular function, Proceedings of the Fourth Annual ASIC Conference and Exhibit (Rochester, 1991)

  • S. Patkar and H. Narayanan, Fast algorithm for the principal partition of a graph, Proceedings of Eleventh Annual Symposium on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-11) LNCS-560 (1991) 288-306

  • H. Narayanan, S. Roy and S. Patkar, Min k-cut and the principal partition of a graph, Proceedings of Second National Seminar on Theoretical Computer Science (India, 1992)

  • V.S. Ovalekar and H. Narayanan, Fast loop matrix generation for hybrid analysis and a comparison of the sparsity of the loop impedance and MNA impedance submatrices, Proceedings of IEEE International Symposium on Circuits and Systems (1992)

  • S. Patkar and H. Narayanan, Principal lattice of partitions of submodular functions on graphs: Fast algorithm for principal partition and generic rigidity, Proceedings of the Third Annual International Symposium on Algorithms and Computation (Nagoya, Japan 1992)

  • S. Patkar and H. Narayanan, Fast sequential and randomized parallel algorithms for rigidity and approximate min-k-cut, Proceedings of Twelfth Annual Symposium on FSTTCS (New Delhi, 1992) (Springer Verlag, 1992)

  • S. Roy and H. Narayanan, Application of the principal partition and principal lattice of partitions of a graph to the problem of decomposition of a finite state machine, Proceedings of the IEEE International Symposium of Circuits and Systems (Chicago, Illinois, 1993)

  • H. Narayanan, S. Patkar and K.V. Subramanian, On the membership problem over polymatroid intersection, Proceedings of the Conference of the European Chapter on Combinatorial Optimization, (Milan, Italy 1994)

  • H. Narayanan, S. Roy and S. Patkar, Approximation algorithms for min-k-overlap using the PLP approach, Proceedings of the Conference on the Mathematical Foundations of Computer Science (Bratislava, Czech Republic, 1994)

  • S.Patkar, S.Batterywala, M.Chandramouli and H.Narayanan, A New Partitioning Strategy Based on Supermodular Functions, Proceedings of 10th International Conference on VLSI Design, Hyderabad, India, (1997) 32-37

  • Shabbir H. Batterywala and H. Narayanan, Time Domain Method for Reduced Order Network Synthesis of Large RC Circuits, The proceedings of the 1998 IEEE International Symposium on Circuits and Systems, VI-82-VI-85, Monterey, California, USA, 1998

  • Shabbir H. Batterywala and H. Narayanan, Efficient DC analysis of RVJ circuits for moment and derivative computations of interconnect networks, Proceedings of 12th international conference in VLSI design, Jan. 1999, 169-174

  • H.Narayanan B.N.V.M. Gupta and M.P.Desai, A state assignment scheme targeting performance and area, Proceedings of 12th international conference in VLSI design, Jan. 1999, 378-383

  • R.Shelar, M.P.Desai and H.Narayanan, Decomposition of Finite State Machines for Area, Delay minimization, Proceedings of the 1999 IEEE International Conference on Computer Design, Austin, Texas, USA

  • Shabbir H. Batterywala and H. Narayanan, Spectral Approximation Method for Choosing `Relevant' Eigenvalues During Interconnect Analysis, Proceedings of the 3rd World Multiconference on Systemics, Cybernetics and Informatics & the 5th International Conference on Information Systems, Analysis and Synthesis, Orlando, USA, September 1999

  • H.Narayanan, On the Duality between Controllability and Observability in Behavioural Systems Theory, Proc. International Conference on Communications Control and Signal Proc. CCSP 2000, Bangalore, July 25-July 28,2000, 183-186

  • R. Shelar, H. Narayanan and M. P. Desai, Orthogonal Partitioning and Gated Clock Architecture for Low Power Realization of FSMs, Proceedings of the 13th Annual IEEE International ASIC/SOC Conference, 13-16 Sept. 2000, Washington,  266-270 (postscript)

  • Sachin B. Patkar, H. Narayanan, Fast Algorithm for Successive Reinforcement of a Network, Proceedings of FSTTCS2000, New Delhi, December 2000

  • H.Narayanan, Matroids representable over Modules, Electrical Network Topology and Behavioural Systems Theory, Research report of the EE Dept., IIT Bombay, May 2000 (postscript).

  • H.Narayanan, Polyhedrally tight functions  and convexity, Invited Talk, ISMP2003, Aug.18-Aug.22, 2003, Copenhagen, Denmark.