Person:
Muthu, Rahul

Profile Picture

Name

Rahul Muthu

Job Title

Faculty

Email Address

Telephone

079-68261564

Birth Date

Specialization

Graph Theory, Data Structures, Algorithms, Automata Theory

Abstract

Biography

I obtained my Ph.D. (2008) in the field of Theoretical Computer Science. The title of my thesis is “Acyclic Edge Colouring: Bounds and Algorithms”. I carried out the research towards my Ph.D. at The Institute of Mathematical Sciences, Chennai, India under the guidance of Prof. C.R. Subramanian. I worked under a post-doctoral fellowship at Laboratoire de Recherche en Informatique, Universite Paris Sud, Orsay, France (2009). I worked in a team headed by Prof. Yannis Manoussakis and conducted research in the field of Structures in Edge Coloured Graphs. I currently work at DA-IICT and my broad research interests lie in the field of Graph Algorithms. I have guided one Ph.D. student, Mahipal Jadeja who defended his thesis (2018) titled “Set Labelling of Vertices and Study of Auxiliary Graphs”. I have also guided around ten M.Tech. Theses and several B.Tech. Projects. My current research problems include: -Defining auxiliary or other graph classes and/or obtaining mathematical characterizations and algorithms for them. -Weight assignment to edges of complete graphs to yield a prespecified number of minimum weight spanning trees. I teach courses in Theoretical Computer Science and Mathematics.

Research Projects

Organizational Units

Name

Filters

2017 - 20194

Settings

search.filters.applied.f.isAuthorOfPublication: search.filters.isAuthorOfPublication.0493af51-b4c6-4c40-84eb-af84bf8eb7d4

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    PublicationMetadata only
    Maximum colored trees in edge-colored graphs
    (Elsevier, 01-08-2019) Borozan, Valentin; Vega, W Fernandez de La; Manoussakis, Yannis; Martinhon, C; Pham, Hong Phong; Saad, Rachid; Muthu, Rahul; DA-IICT, Gandhinagar
    We consider maximum properly edge-colored�trees�in edge-colored graphs. We also consider the problem where, given a vertex�, determine whether the graph has a spanning tree rooted at�, such that all root-to-leaf paths are properly�colored. We consider these problems from graph-theoretic as well as algorithmic viewpoints. We prove their optimization versions to be NP-hard in general and provide algorithms for graphs without properly edge-colored cycles. We also derive some nonapproximability bounds. A study of the trends random graphs display with regard to the presence of properly edge-colored spanning trees is presented.
  • Thumbnail Image
    PublicationMetadata only
    Uniform set labeling vertices to ensure adjacency coincides with disjointness
    (Journal of Mathematical and Computational Science, 01-04-2017) Jadeja, Mahipal; Muthu, Rahul; DA-IICT, Gandhinagar; Jadeja, Mahipal (201221015)
    Given a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. Sometimes these sets are finite, but in many well known examples like geometric graphs (including interval graphs) they are infinite. One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency coincides with intersection of the corresponding sets. The sets are usually required to conform to some template, depending on the problem, to be either a finite set, or some geometric set like intervals, circles, discs, cubes etc. The problem of representing a graph as an intersection graph of sets was first introduced by Erdos [Alon, Noga, Covering graphs by the minimum number of equivalence relations, Combinatorica 6(1986), 201�206] and they looked at minimising the underlying universal set necessary to represent any given graph. In that paper it was shown that the problem is NP complete. In this paper we study a natural variant of this problem which is to consider graphs where vertices represent distinct sets and adjacency coincides with disjointness. Although this is nearly the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. The parameter we take into account is the minimum universe size possible (disregarding individual label sizes).
  • Thumbnail Image
    PublicationMetadata only
    Labeled object treemap: A new graph labeling based technique for visualizing multiple hierarchies
    (APAM, 01-01-2017) Jadeja, Mahipal; Muthu, Rahul; DA-IICT, Gandhinagar; Jadeja, Mahipal (201221015)
    ormation visualization is a class of techniques which is used to present data in a graphical or pictorial format. Identification of new patterns as well as an understanding of difficult concepts is possible with the proper use of visualization. Using interactive visualization, various other details related to the information can be obtained. In this paper, we consider trees in which each node is related to a leaf node (object) of taxonomy. We propose a new technique of visualization namely �Labeled Object Treemap� for the visualization of multiple hierarchies. In our approach, a unique label is associated with each node and this label will convey all the necessary information including adjacency as well as non-adjacency with the other nodes of the tree. The comparison of our proposed technique with already known techniques is also made. Here we develop and use a labeling of trees where vertices represent distinct sets and adjacency coincides with disjointness. The total number of distinct elements used in the underlying labeling is asymptotically minimized. The motivation of selecting set labeling is to use cardinalities of labels to identify level numbers of the underlying tree using which it will be easier to discover adjacency as well as non-adjacency for all vertices. Our motivation to look at disjointness instead of intersection is that several well-known graphs like the Petersen graph and Kneser graphs are expressed in the latter method. Our main contribution is the development of a new visualization technique which solves the issues of edge crossing and continuity of the 'Trees in a treemap' visualization technique while maintaining all the good characteristics of existing methods for visualizing multiple hierarchies. Additional features are also discussed using the modified labeling algorithm.
  • Thumbnail Image
    PublicationMetadata only
    Set Labelling Vertices To Ensure Adjacency Coincides With Disjointness
    (Elsevier, 01-12-2017) Jadeja, Mahipal; Muthu, Rahul; V, Sunitha; DA-IICT, Gandhinagar; Jadeja, Mahipal (201221015)
    Given a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. Sometimes these sets are finite, but in many well known examples like geometric graphs (including interval graphs) they are infinite. One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency coincides with intersection of the corresponding sets. The sets are usually required to conform to some template, depending on the problem, to be either a finite set, or some geometric set like intervals, circles, discs, cubes etc. The problem of representing a graph as an intersection graph of sets was first introduced by Erdos [Alon, Noga, Covering graphs by the minimum number of equivalence relations, Combinatorica 6(1986), 201�206] and they looked at minimising the underlying universal set necessary to represent any given graph. In that paper it was shown that the problem is NP complete. In this paper we study a natural variant of this problem which is to consider graphs where vertices represent distinct sets and adjacency coincides with disjointness. Although this is nearly the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. The parameter we take into account is the minimum universe size possible (disregarding individual label sizes).