Conference Papers
Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506
Browse
4 results
Search Results
Item Parameterized algorithms for survivable network design with uniform demands(Association for Computing Machinery acmhelp@acm.org, 2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-Edge Connected Subgraph ( λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-Vertex Connected Subgraph ( λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that λ-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. © Copyright 2018 by SIAM.Item Ramsey Numbers for Line Graphs(Springer, 2020) Abbasi, H.; Basavaraju, M.; Gurushankar, E.; Jivani, Y.; Srikanth, D.Given a graph, the classical Ramsey number R(k, l) is the least number of vertices that need to be in the graph for the existence of a clique of size k or an independent set of size l. Finding R(k, l) exactly has been a notoriously hard problem. Even R(k, 3) has not been determined for all values of k. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph L(G) is equivalent to the minimum number of edges the underlying graph G needs to have for the existence of a vertex with degree k or a matching of size l. Chvátal and Hanson determined this exactly for line graphs of simple graphs. Later Balachandran and Khare gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chvátal and Hanson. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs. © 2020, Springer Nature Switzerland AG.Item The Linear Arboricity Conjecture for 3-Degenerate Graphs(Springer Science and Business Media Deutschland GmbH info@springer-sbm.com, 2020) Basavaraju, M.; Bishnu, A.; Francis, M.; Pattanayak, D.A k-linear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear forest—a forest whose each connected component is a path. The linear arboricity χl′(G) of G is the minimum integer k such that there exists a k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, χl′(G)≤⌈Δ(G)+12⌉ where Δ(G) is the maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for triangle-free planar graphs. Our proof also yields an O(n)-time algorithm that partitions the edge set of any 3-degenerate graph G on n vertices into at most ⌈Δ(G)+12⌉ linear forests. Since χl′(G)≥⌈Δ(G)2⌉ for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1. © 2020, Springer Nature Switzerland AG.Item Vehicular Pollution and Its Relationship with Meteorological Variables at Toll Plaza During Paryaya Festival in Udupi, Karnataka(Springer Science and Business Media Deutschland GmbH, 2024) Charly, T.; Basavaraju, M.; Mulangi, R.H.The quantification of both air pollutants and noise is important to understand the impact of festival on pollution at toll plaza. Toll plazas can cause deterioration of air quality due to increased emission of pollutants caused by stop and go process. The present study was conducted at a toll plaza in front of National Institute of Technology, Karnataka, which is 39 kms from Udupi, Karnataka, to assess the impact of vehicular movement due to Paryaya festival, which was on the third week of January 2020 at Udupi, on noise and air pollution at study area. Data regarding meteorological parameters and traffic volume were also considered during the study. Experiments were carried out at toll plaza for one week, including pre- and post-festival days. In this study, a spearman correlation matrix between air pollutants and meteorological parameters (temperature, pressure, precipitable water content, relative humidity, and wind speed) were also investigated. The concentration of air pollutants (TSPM, SO2, CO2) and noise were more on the day of festival as the number of vehicles plying on the road was higher in number. Maximum positive correlation was observed between concentration of CO and precipitable water content (Ï â€‰= 0.900) and minimum between SO2 and precipitable water content (Ï â€‰= 0.000). Precipitable water content was positively correlated with all air pollutants (TSPM, NO2, CO, and CO2), and no correlation was observed with SO2. The results show the impact of increase in vehicular movement due to festival on the quality of ambient air and role of meteorology on urban air pollution. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.