Computer Science and Engineeringhttp://repository.iitgn.ac.in/handle/123456789/4272017-08-23T15:45:11Z2017-08-23T15:45:11ZAdvances in conceptual modelingJeusfeld, Manfred A.Karlapalem, Kamalakarhttp://repository.iitgn.ac.in/handle/123456789/19872015-12-01T06:42:13Z2015-01-01T00:00:00ZAdvances in conceptual modeling
Jeusfeld, Manfred A.; Karlapalem, Kamalakar
2015-01-01T00:00:00ZPolynomial-time algorithm for Isomorphism of graphs with clique-width at most 3Das, BireswarEnduri, Murali KrishnaReddy, I. Vinodhttp://repository.iitgn.ac.in/handle/123456789/17932015-06-26T11:07:08Z2015-06-01T00:00:00ZPolynomial-time algorithm for Isomorphism of graphs with clique-width at most 3
Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod
The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. While there are many results on the graph isomorphism problem for bounded tree-width graphs, very little is known about isomorphism of bounded clique-width graphs. We give the first polynomial-time graph isomorphism algorithm for graphs with clique-width at most 3.
2015-06-01T00:00:00ZLogspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphsDas, BireswarEnduri, Murali KrishnaReddy, I. Vinodhttp://repository.iitgn.ac.in/handle/123456789/16312015-10-13T07:07:42Z2015-02-01T00:00:00ZLogspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod
We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded tree-depth. We also show that the graph isomorphism problem is fixed parameter tractable for a related parameterized graph class where the graph parameter is the length of the longest cycle.
2015-02-01T00:00:00ZOn learning mixture models for permutationsChierichetti, FlavioDasgupta, AnirbanKumar, RaviLattanzi, Silviohttp://repository.iitgn.ac.in/handle/123456789/15872015-01-21T11:03:01Z2015-01-02T00:00:00ZOn learning mixture models for permutations
Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi; Lattanzi, Silvio
In this paper we consider the problem of learning a mixture of permutations, where each component of the mixture is generated by a stochastic process. Learning permutation mixtures arises in practical settings when a set of items is ranked by different sub-populations and the rankings of users in a sub-population tend to agree with each other. While there is some applied work on learning such mixtures, they have been mostly heuristic in nature.
We study the problem where the permutations in a mixture component are generated by the classical Mallows process in which each component is associated with a center and a scalar parameter. We show that even when the centers are arbitrarily separated, with exponentially many samples one can learn the mixture, provided the parameters are all the same and known; we also show that the latter two assumptions are information-theoretically inevitable. We then focus on polynomial-time learnability and show bounds on the performance of two simple algorithms for the case when the centers are well separated.
Conceptually, our work suggests that while permutations may not enjoy as nice mathematical properties as Gaussians, certain structural aspects can still be exploited towards analyzing the corresponding mixture learning problem.
2015-01-02T00:00:00Z