Subjects

Subjects

Sort by: Order: Results:

  • Generic Single Edge Fault Tolerant Exact Distance Oracle 
    Gupta, Manoj; Singh, Aditi (Cornell University Library, 2018-05)
    Given an undirected unweighted graph G and a source set S of |S|=? sources, we want to build a data structure which can process the following query {\sc Q}(s,t,e): find the shortest distance from s to t avoiding an edge ...
  • Maximum Matchings via Glauber Dynamics 
    Jindal, Anant; Kochar, Gazal; Pal, Manjish (arXiv, Cornell University Library, 2011-07)
    In this paper we study the classic problem of computing a maximum cardinality matching in general graphs G=(V,E). The best known algorithm for this problem till date runs in O(mn√) time due to Micali and Vazirani \cite{MV80}. ...
  • On additive approximate submodularity 
    Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi (Cornell University Library, 2020-10)
  • On fair division with binary valuations respecting social networks 
    Misra, Neeldhara; Nayak, Debanuj (Cornell University Library, 2021-11)
    We study the computational complexity of finding fair allocations of indivisible goods in the setting where a social network on the agents is given. Notions of fairness in this context are "localized", that is, agents are ...
  • The isomorphism problem of power graphs and a question of cameron 
    Das, Bireswar; Ghosh, Jinia; Kumar, Anant (Cornell University Library, 2023-05)
    The isomorphism problem for graphs (GI) and the isomorphism problem for groups (GrISO) have been studied extensively by researchers. The current best algorithms for both these problems run in quasipolynomial time. In this ...

Search Digital Repository


Browse

My Account