Publications

  1. Shiva Kintali, Qiuyi Zhang
    Forbidden Directed Minors and Directed Pathwidth    [pdf (coming soon)]
    Under Preparation.
    keywords : treewidth, pathwidth, Kelly-width, directed pathwidth, graph minors

  2. Shiva Kintali, Qiuyi Zhang
    Forbidden Directed Minors and Kelly-width    [pdf at arXiv]
    Preprint.
    keywords : treewidth, pathwidth, Kelly-width, directed pathwidth, graph minors

  3. Shiva Kintali
    Directed Minors IV : Avoiding a partial k-DAG    [pdf (coming soon)]
    Under Preparation.
    keywords : treewidth, pathwidth, Kelly-width, directed pathwidth, graph minors

  4. Shiva Kintali
    Directed Minors III : Orientations of partial k-trees    [pdf (coming soon)]
    Under Preparation.
    keywords : treewidth, pathwidth, Kelly-width, directed pathwidth, graph minors

  5. Shiva Kintali
    Directed Minors II : Directed Grid Minor Theorem    [pdf (coming soon)]
    Under Preparation.
    keywords : treewidth, pathwidth, Kelly-width, directed pathwidth, graph minors

  6. Shiva Kintali
    Directed Minors I    [pdf (coming soon)]
    Under Preparation.
    keywords : treewidth, pathwidth, Kelly-width, directed pathwidth, graph minors

  7. Aviv Adler, Shiva Kintali
    Reconstruction of 4-trees    [pdf (coming soon)]
    Under Preparation.
    keywords : Graph Reconstruction Conjecture

  8. Shiva Kintali, Sinziana Munteanu
    Computing Bounded Path Decompositions in Logspace    [pdf at ECCC]
    Preprint
    keywords : Logspace, Path Decompositions, Pathwidth, Tree Decompositions, Treewidth

  9. Shiva Kintali, Asaf Shapira
    A Note on the Balanced ST-Connectivity    [pdf at arXiv]
    Preprint
    keywords : balanced st-connectivity, space-bounded computation, LogCFL, auxiliary pushdown automata

  10. Parinya Chalermsook,  Shiva Kintali,  Richard Lipton,  Danupon Nanongkai
    Graph Pricing Problem on Bounded Tree-width, Bounded Genus and k-partite graphs    [pdf at arXiv]
    Submitted to a Journal
    keywords : graph vertex pricing, single-minded pricing, Sherali-Adams relaxation

  11. Shiva Kintali, Nishad Kothari, Akash Kumar
    Approximation Algorithms for Directed Width Parameters    [pdf at arXiv]
    Submitted to a Journal
    keywords : directed treewidth, D-width, DAG-width, Kelly-width, directed pathwidth

  12. Shiva Kintali.
    Realizable Paths and the NL vs L Problem    [pdf at ECCC]
    Preprint
    keywords : Savitch's theorem, space-bounded computation, LogCFL, auxiliary pushdown automata

  13. Shiva Kintali
    A Generalization of Erdos's Proof of Bertrand-Chebyshev Theorem    [pdf]
    Submitted to a Journal
    keywords : Combinatorial Number Theory

  14. Shiva Kintali,  Laura J. Poplawski,  Rajmohan Rajaraman,  Ravi Sundaram,  Shang-Hua Teng
    Reducibility Among Fractional Stability Problems    [full version pdf, full version ps, FOCS version ]
    Journal version to appear in SIAM Journal of Computing.
    In Proceedings of 50th FOCS. 2009. Atlanta, Georgia.
    keywords : algorithmic game theory, PPAD complexity class, hardness of approximation, Fractional Stable Paths Problem, Core of Balanced Games, Scarf's Lemma, Fractional Hypergraph Matching, Budget Connection Games, Fractional Kernel.

  15. Shiva Kintali.
    SCARF is PPAD-complete    [pdf at arXiv]
    Manuscript
    keywords : Scarf's Lemma, PPAD complexity class, Fractional Stable Paths Problem, Fractional Kernel

  16. David A. Bader, Shiva Kintali, Kamesh Madduri, Milena Mihail.
    Approximating Betweenness Centrality    [pdf]
    In the Proceedings of Workshop On Algorithms And Models For The Web-Graph (WAW) 2007, WAW 2007.
    keywords : approximation algorithms, centrality metrics, social networks

  17. Shiva Kintali.
    A Distributed Protocol for Fractional Stable Paths Problem    [pdf]
    Presented at the DIMACS/DyDAn Workshop on Secure Internet Routing, Rutgers University, March 24-26, 2008
    Georgia Tech, College of Computing Technical Report GT-CS-08-06
    keywords : distributed algorithms, routing algorithms, border gateway protocol, nash equilibrium

  18. Shiva Kintali.
    Betweenness Centrality : Algorithms and Lower Bounds    [pdf]
    Georgia Tech, College of Computing Technical Report GT-CS-09-10
    keywords : centrality metrics, parallel algorithms, social networks, lower bounds.

  19. Chun Chen, Jaewook Shin, Shiva Kintali, Jacqueline Chame, Mary Hall
    Model-Guided Empirical Optimization for Multimedia Extension Architectures.
    POHLL 2007 (In association with IPDPS 2007)

  20. Shiva Kintali.
    MxYacc: Parser Generator for Mixed Languages.
    SIGPLAN Notices 41(2): 25-28 (2006)

  21. Shiva Kintali.
    Efficiently Parsing Mixed Languages.
    ANTLR Workshop 2004

  22. Sudeshna Sarkar, K Shivaprasad, Rajib Lochan Saha and Supradeep Barua.
    Conversion of unstructured text to structured hypertext form,
    International Forum cum Conference on Information Technology and Communication at the Dawn of the New Millennium August 1-4, 2000, Bangkok, Thailand, pp 99-109.