Search

Your search keyword '"Subramanian, C. R."' showing total 134 results
Start Over Author "Subramanian, C. R."
134 results on '"Subramanian, C. R."'

2. Approximating MIS over equilateral $B_1$-VPG graphs

Author

Lahiri, Abhiruk, Mukherjee, Joydeep, and Subramanian, C. R.

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We present an approximation algorithm for the maximum independent set (MIS) problem over the class of equilateral $B_1$-VPG graphs. These are intersection graphs of $L$-shaped planar objects % (and their rotations by multiples of $90^o$) with both arms of each object being equal. We obtain a $36(\log 2d)$-approximate algorithm running in $O(n(\log n)^2)$ time for this problem, where $d$ is the ratio $d_{max}/d_{min}$ and $d_{max}$ and $d_{min}$ denote respectively the maximum and minimum length of any arm in the input equilateral $L$-representation of the graph. In particular, we obtain $O(1)$-factor approximation of MIS for $B_1$-VPG -graphs for which the ratio $d$ is bounded by a constant. % formed by unit length $L$-shapes. In fact, algorithm can be generalized to an $O(n(\log n)^2)$ time and a $36(\log 2d_x)(\log 2d_y)$-approximate MIS algorithm over arbitrary $B_1$-VPG graphs. Here, $d_x$ and $d_y$ denote respectively the analogues of $d$ when restricted to only horizontal and vertical arms of members of the input. This is an improvement over the previously best $n^\epsilon$-approximate algorithm \cite{FoxP} (for some fixed $\epsilon>0$), unless the ratio $d$ is exponentially large in $n$. In particular, $O(1)$-approximation of MIS is achieved for graphs with $\max\{d_x,d_y\}=O(1)$.

Published
2019

3. 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

4. Inductive Graph Invariants and Algorithmic Applications

Author

Subramanian, C. R., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Wu, Weili, editor, and Zhang, Zhongnan, editor

Published
2020
Full Text
View/download PDF

5. New lower bounds for the independence number of sparse graphs and hypergraphs

Author

Dutta, Kunal, Mubayi, Dhruv, and Subramanian, C. R.

Subjects
Mathematics - Combinatorics, 05D40
Abstract

We obtain new lower bounds for the independence number of $K_r$-free graphs and linear $k$-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza \cite{CT91}. Our proof technique is an extension of a method of Caro and Wei \cite{CA79, WE79}, and we also give a new short proof of the main result of \cite{CT91} using this approach. As byproducts, we also obtain some non-trivial identities involving binomial coefficients.

Published
2011

7. Maximum Independent Set on -VPG Graphs

Author

Lahiri, Abhiruk, Mukherjee, Joydeep, Subramanian, C. R., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Lu, Zaixin, editor, Kim, Donghyun, editor, Wu, Weili, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2015
Full Text
View/download PDF

8. Probabilistic Arguments in Graph Coloring (Invited Talk)

Author

Subramanian, C. R., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Ganguly, Sumit, editor, and Krishnamurti, Ramesh, editor

Published
2015
Full Text
View/download PDF

11. Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration

Author

Dutta, Kunal, 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, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and López-Ortiz, Alejandro, editor

Published
2010
Full Text
View/download PDF

12. Forbidden Subgraph Colorings and the Oriented Chromatic Number

Author

Aravind, N. R., 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, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fiala, Jiří, editor, Kratochvíl, Jan, editor, and Miller, Mirka, editor

Published
2009
Full Text
View/download PDF

13. 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

14. The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number

Author

Mishra, Sounaka, Raman, Venkatesh, Saurabh, Saket, Sikdar, Somnath, 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, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Tokuyama, Takeshi, editor

Published
2007
Full Text
View/download PDF

15. 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

24. Coloring random graphs

Author

Fürer, Martin, Subramanian, C. R., Goos, Gerhard, editor, Hartmanis, Juris, editor, Nurmi, Otto, editor, and Ukkonen, Esko, editor

Published
1992
Full Text
View/download PDF

30. On approximating MIS over B1-VPG graphs.

Author

Lahiri, Abhiruk, Mukherjee, Joydeep, and Subramanian, C. R.

Subjects
INTERSECTION numbers, INDEPENDENT sets, APPROXIMATION algorithms, INTERSECTION graph theory, ALGORITHMS
Abstract

In this paper, we present an approximation algorithm for the maximum independent set (MIS) problem over the class of B 1 -VPG graphs when the input is specified by a B 1 -VPG representation. We obtain a 6 (log n) 2 -approximation algorithm running in O (n (log n) 3) time. This is an improvement over the previously best n -approximation algorithm [J. Fox and J. Pach, Computing the independence number of intersection graphs, in Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2011), 2011, pp. 1161–1165, doi:10.1137/1.9781611973082.87] (for some fixed > 0) designed for some subclasses of string graphs, on B 1 -VPG graphs. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

39. INTERSECTION DIMENSION AND GRAPH INVARIANTS.

Author

ARAVIND, N. R. and SUBRAMANIAN, C. R.

Subjects
*PERMUTATIONS
Abstract

We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree is at most O (log /log)· It is also shown that permutation dimension of any graph is at most (log) 1+o(1). We also obtain bounds on intersection dimension in terms of treewidth. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results