Mathematics
http://repository.iitgn.ac.in/handle/123456789/547
Thu, 24 May 2018 21:27:23 GMT2018-05-24T21:27:23ZParameterized algorithms for Max Colorable induced subgraph problem on perfect graphs
http://repository.iitgn.ac.in/handle/123456789/3632
Parameterized algorithms for Max Colorable induced subgraph problem on perfect graphs
Misra, Neeldhara; Panolan, Fahad; Rai, Ashutosh; Raman, Venkatesh; Saurabh, Saket
We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133�137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an nO(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by ? , the number of vertices in the solution, we give two fixed-parameter tractable algorithms.The first algorithm runs in time 5.44?(n+t)O(1) where t is the number of maximal independent sets of the input graph.The second algorithm runs in time O(6.75?+o(?)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time.The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense:(a)
On split graphs, we do not expect a polynomial kernel if q is a part of the input.On perfect graphs, we do not expect a polynomial kernel even for fixed values of q?2
Sun, 01 Apr 2018 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/36322018-04-01T00:00:00ZEigenvalue problem for fractional Kirchhoff Laplacian
http://repository.iitgn.ac.in/handle/123456789/3633
Eigenvalue problem for fractional Kirchhoff Laplacian
Tyagi, Jagmohan
In this note, we discuss the isolatedness, simplicity and nodal estimate for the first eigenvalue of fractional Laplacian of Kirchhoff type. This work is motivated by the recent works on the fractional eigenvalues.
Sun, 01 Apr 2018 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/36332018-04-01T00:00:00ZInformation-sharing and decision-making in networks of radiation detectors
http://repository.iitgn.ac.in/handle/123456789/3493
Information-sharing and decision-making in networks of radiation detectors
Yadav, Indrajeet; Pahlajani, Chetan D.; Tanner, Herbert G.; Poulakakis, Ioannis
A network of sensors observes a time-inhomo-geneous Poisson signal and within a fixed time interval has to decide between two hypotheses regarding the signal’s intensity. The paper reveals an interplay between network topology, essentially determining the quantity of information available to different sensors, and the quality of individual sensor information as captured by the sensor’s likelihood ratio. Armed with analytic expressions of bounds on the error probabilities associated with the binary hypothesis test regarding the intensity of the observed signal, the insight into the interplay between sensor communication and data quality helps in deciding which sensor is better positioned to make a decision on behalf of the network, and links the analysis to network centrality concepts. The analysis is illustrated on networked radiation detection examples, first in simulation and then on cases utilizing field measurement data available through a U.S. Domestic Nuclear Detection Office (dndo) database.
Thu, 01 Feb 2018 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/34932018-02-01T00:00:00ZFrobenius number and minimal presentation of certain numerical semigroups
http://repository.iitgn.ac.in/handle/123456789/3483
Frobenius number and minimal presentation of certain numerical semigroups
Mehta, Ranjana; Saha, Joydip; Sengupta, Indranath
Suppose e≥4 be an integer, a=e+1, b>a+(e−3)d, gcd(a,d)=1 and d∤(b−a). Let M={a,a+d,a+2d,…,a+(e−3)d,b,b+d}, which forms a minimal generating set for the numerical semigroup Γe(M), generated by the set M. We calculate the Ap\'{e}ry set and the Frobenius number of Γe(M). We also show that the minimal number of generators for the defining ideal p of the affine monomial curve parametrized by X0=ta, X1=ta+d,…,Xe−3=ta+(e−3)d, Xe−2=tb, Xe−1=tb+d is a bounded function of e.
Thu, 01 Feb 2018 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/34832018-02-01T00:00:00Z