Computer Science and Engineering
http://repository.iitgn.ac.in/handle/123456789/427
Wed, 23 Aug 2017 15:45:58 GMT2017-08-23T15:45:58ZAdvances in conceptual modeling
http://repository.iitgn.ac.in/handle/123456789/1987
Advances in conceptual modeling
Jeusfeld, Manfred A.; Karlapalem, Kamalakar
Thu, 01 Jan 2015 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/19872015-01-01T00:00:00ZPolynomial-time algorithm for Isomorphism of graphs with clique-width at most 3
http://repository.iitgn.ac.in/handle/123456789/1793
Polynomial-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.
Mon, 01 Jun 2015 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/17932015-06-01T00:00:00ZLogspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
http://repository.iitgn.ac.in/handle/123456789/1631
Logspace 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.
Sun, 01 Feb 2015 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/16312015-02-01T00:00:00ZOn learning mixture models for permutations
http://repository.iitgn.ac.in/handle/123456789/1587
On 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.
Fri, 02 Jan 2015 00:00:00 GMThttp://repository.iitgn.ac.in/handle/123456789/15872015-01-02T00:00:00Z