Search

Your search keyword '"Muthu, Rahul"' showing total 73 results
Start Over Author "Muthu, Rahul"

Refine your results

more »

more »

more »
73 results on '"Muthu, Rahul"'

1. Exactly k MSTs: How Many Vertices Suffice?

Author

Dutta, Apratim, Muthu, Rahul, Tawari, Anuj, Sunitha, V., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Wu, Weili, editor, and Guo, Jianxiong, editor

Published
2024
Full Text
View/download PDF

3. Edgeless Graph: A New Graph-Based Information Visualization Technique

Author

Jadeja, Mahipal, Muthu, Rahul, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Sahni, Manoj, editor, Merigó, José M., editor, Jha, Brajesh Kumar, editor, and Verma, Rajkumar, editor

Published
2021
Full Text
View/download PDF

4. Interactive Labelled Object Treemap: Visualization Tool for Multiple Hierarchies

Author

Jadeja, Mahipal, Kanakia, Hitarth, Muthu, Rahul, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Bhateja, Vikrant, editor, Peng, Sheng-Lung, editor, Satapathy, Suresh Chandra, editor, and Zhang, Yu-Dong, editor

Published
2021
Full Text
View/download PDF

5. Spanning Tree Auxiliary Graphs

Author

Garg, Abhishek, Jadeja, Mahipal, and Muthu, Rahul

Subjects
Mathematics - Combinatorics
Abstract

In this paper, we define a class of auxiliary graphs associated with simple undirected graphs. This class of auxiliary graphs is based on the set of spanning trees of the original graph and the edges constituting those spanning trees. A class of auxiliary graphs can be viewed as a function from the class of graphs to the class of graphs. We provide mathematical characterisation of graphs which are the spanning tree auxiliary graphs of some simple graph. Since the class of spanning tree auxiliary graphs of graphs do not have unique preimages (the forward function is not injective), we derive precisely the classes of graphs which have the same auxiliary graph. We design algorithms for computing a basic preimage and define rules to get other solutions for the same auxiliary graph. We also obtain several results expressing parameters of the auxiliary graph in terms of (not necessarily the same) parameters of the original graph.

Published
2017

6. A New Characterisation of Total Graphs

Author

Goyal, Ravi, Jadeja, Mahipal, and Muthu, Rahul

Subjects
Mathematics - General Mathematics
Abstract

Graphs constructed to translate some graph problem into another graph problem are usually called auxiliary graphs. Specifically total graphs of simple graphs are used to translate the total colouring problem of the original graph into a vertex colouring problem of the transformed graph. In this paper, we obtain a new characterisation of total graphs of simple graphs. We also design algorithms to compute the inverse total graphs when the input graph is a total graph. These results improve over the work of Behzad, by using novel observations on the properties of the local structure in the neighbourhood of each vertex. The earlier algorithm was based on bfs and distances. Our theorems result in partitioning the vertex set of the total graph into the original graph and the line graph efficiently. We obtain constructive results for special classes, most notably for total graph of complete graphs.

Published
2016

7. Labelling vertices to ensure adjacency coincides with disjointness

Author

Jadeja, Mahipal, Muthu, Rahul, and V, Sunitha

Subjects
Mathematics - General Mathematics
Abstract

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 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 really the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. When taken across the spectrum of all graphs the two problems are evidently identical. Our motivation to look at disjointness instead of intersection is that several well known graphs like the Petersen graph and Knesser graphs are expressed in the latter method, and the complements of these families are not well studied. The parameters we take into account are the maximum size of an individual vertex label, minimum universe size possible (disregarding individual label sizes) and versions of these two where it is required that each vertex gets labels of the same size.

Published
2016

8. Cartesian Product and Acyclic Edge Colouring

Author

Muthu, Rahul and Subramanian, C. R.

Subjects
Mathematics - Combinatorics
Abstract

The acyclic chromatic index, denoted by $a'(G)$, of a graph $G$ is the minimum number of colours used in any proper edge colouring of $G$ such that the union of any two colour classes does not contain a cycle, that is, forms a forest. We show that $a'(G\Box H)\le a'(G) + a'(H)$ for any two graphs $G$ and $H$ such that $max\{a'(G), a'(H)\} > 1$. Here, $G \Box H$ denotes the cartesian product of $G$ and $H$. This extends a recent result of [15] where tight and constructive bounds on $a'(G)$ were obtained for a class of grid-like graphs which can be expressed as the cartesian product of a number of paths and cycles.

Published
2015

9. Improved Upper Bounds on $a'(G\Box H)$

Author

Mehta, Punit, Muthu, Rahul, Patel, Gaurav, Thakkar, Om, and Vyas, Devanshi

Subjects
Mathematics - Combinatorics, Computer Science - Discrete Mathematics
Abstract

The acyclic edge colouring problem is extensively studied in graph theory. The corner-stone of this field is a conjecture of Alon et. al.\cite{alonacyclic} that $a'(G)\le \Delta(G)+2$. In that and subsequent work, $a'(G)$ is typically bounded in terms of $\Delta(G)$. Motivated by this we introduce a term $gap(G)$ defined as $gap(G)=a'(G)-\Delta(G)$. Alon's conjecture can be rephrased as $gap(G)\le2$ for all graphs $G$. In \cite{manusccartprod} it was shown that $a'(G\Box H)\le a'(G)+a'(H)$, under some assumptions. Based on Alon's conjecture, we conjecture that $a'(G\Box H)\le a'(G)+\Delta(H)$ under the same assumptions, resulting in a strengthening. The results of \cite{alonacyclic} validate our conjecture for the class of graphs it considers. We prove our conjecture for a significant subclass of sub-cubic graphs and state some generic conditions under which our conjecture can be proved. We suggest how our technique can be potentially applied by future researchers to expand the class of graphs for which our conjecture holds. Our results improve the understanding of the relationship between Cartesian Product and acyclic chromatic index., Comment: 10 pages, 5 figures

Published
2015

11. Acyclic Edge Colouring of Outerplanar Graphs

Author

Muthu, Rahul, Narayanan, N., Subramanian, C. R., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Rangan, C. Pandu, editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kao, Ming-Yang, editor, and Li, Xiang-Yang, editor

Published
2007
Full Text
View/download PDF

12. Optimal Acyclic Edge Colouring of Grid Like Graphs

Author

Muthu, Rahul, Narayanan, N., Subramanian, C. R., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Chen, Danny Z., editor, and Lee, D. T., editor

Published
2006
Full Text
View/download PDF

19. Acyclic Edge Colouring of Outerplanar Graphs.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Ming-Yang Kao, Xiang-Yang Li, Muthu, Rahul, Narayanan, N., and Subramanian, C. R.

Abstract

An acyclic edge colouring of a graph is a proper edge colouring having no 2-coloured cycle, that is, a colouring in which the union of any two colour classes forms a linear forest. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge colouring using k colours and is usually denoted by a′(G). Determining a′(G) exactly is a very hard problem (both theoretically and algorithmically) and is not determined even for complete graphs. We show that a′(G) ≤ Δ(G) + 1, if G is an outerplanar graph. This bound is tight within an additive factor of 1 from optimality. Our proof is constructive leading to an time algorithm. Here, Δ = Δ(G) denotes the maximum degree of the input graph. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

20. Optimal Acyclic Edge Colouring of Grid Like Graphs.

Author

Chen, Danny Z., Lee, D. T., Muthu, Rahul, Narayanan, N., and Subramanian, C. R.

Abstract

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the Cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes (hypergrids), hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time. Keywords: Acyclic Edge Colouring, Graph, Acyclic Chromatic Index, Mesh, Hypercube, Tori. [ABSTRACT FROM AUTHOR]

Published
2006
Full Text
View/download PDF

21. Cyclability, Connectivity and Circumference

Author

Balachandran, Niranjan, Hebbar, Anish, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

23. Structural Parameterization of Alliance Problems

Author

Reddy, Sangam Balchandar, Kare, Anjeneya Swami, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

24. Coloring of a Superclass of -free graphs

Author

Prashant, Athmakoori, Raj, S. Francis, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

25. On Structural Parameterizations of Star Coloring

Author

Bhyravarapu, Sriram, Reddy, I. Vinod, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

26. Axiomatic Characterization of the Toll Walk Function of Some Graph Classes

Author

Sheela, Lekshmi Kamal K., Changat, Manoj, Peterin, Iztok, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

27. Graph Covering Using Bounded Size Subgraphs

Author

Gorain, Barun, Patra, Shaswati, Singh, Rishi Ranjan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

28. Maximum Subgraph Problem for 3-Regular Knödel graphs and its Wirelength

Author

Rajan, R. Sundara, Reji, Remi Mariam, Rajalaxmi, T. M., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

29. Transitivity on Subclasses of Chordal Graphs

Author

Paul, Subhabrata, Santra, Kamal, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

30. Complexity Results on Cosecure Domination in Graphs

Author

Kusum, Pandey, Arti, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

32. Minimum Maximal Acyclic Matching in Proper Interval Graphs

Author

Chaudhary, Juhi, Mishra, Sounaka, Panda, B. S., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

34. Mind the Gap: Edge Facility Location Problems in Theory and Practice

Author

Beck, Moritz, Spoerhase, Joachim, Storandt, Sabine, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

35. Latin Hexahedra and Related Combinatorial Structures

Author

Yamamura, Akihiro, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

36. Cops and Robber on Oriented Graphs with Respect to Push Operation

Author

Das, Sandip, Gahlawat, Harmender, Ramgopal, Ashwin, Sahoo, Uma Kant, Sen, Sagnik, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

37. Computational Aspects of Double Dominating Sequences in Graphs

Author

Sharma, Gopika, Pandey, Arti, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

38. On Three Domination-Based Identification Problems in Block Graphs

Author

Chakraborty, Dipayan, Foucaud, Florent, Parreau, Aline, Wagler, Annegret K., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

39. Monitoring Edge-Geodetic Sets in Graphs

Author

Foucaud, Florent, Narayanan, Krishna, Ramasubramony Sulochana, Lekshmi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

40. New Bounds and Constructions for Neighbor-Locating Colorings of Graphs

Author

Chakraborty, Dipayan, Foucaud, Florent, Nandi, Soumen, Sen, Sagnik, Supraja, D. K., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

43. On Coupon Coloring of Cayley Graphs

Author

Thankachan, Reji, Rajamani, Pavithra, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

44. Rectilinear Voronoi Games with a Simple Rectilinear Obstacle in Plane

Author

Das, Arun Kumar, Das, Sandip, Maheshwari, Anil, Sarvottamananda, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

45. Fault-Tolerant Dispersion of Mobile Robots

Author

Chand, Prabhat Kumar, Kumar, Manish, Molla, Anisur Rahaman, Sivasubramaniam, Sumathi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

46. Arbitrary-Oriented Color Spanning Region for Line Segments

Author

Maji, Sukanya, Sadhu, Sanjib, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

47. Perfectness of G-generalized Join of Graphs

Author

Kavaskar, T., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

48. On Locally Identifying Coloring of Graphs

Author

Bhyravarapu, Sriram, Kumari, Swati, Reddy, I. Vinod, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

49. 5-List Coloring Toroidal 6-Regular Triangulations in Linear Time

Author

Balachandran, Niranjan, Sankarnarayanan, Brahadeesh, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

50. Efficient Reductions and Algorithms for Subset Product

Author

Dutta, Pranjal, Rajasree, Mahesh Sreekumar, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bagchi, Amitabha, editor, and Muthu, Rahul, editor

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results