NDLI: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

Please wait, while we are loading the content...

Confronting hardness using a hybrid approach

A new approach to proving upper bounds for MAX-2-SAT

Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity

Local versus global properties of metric spaces

Directed metrics and directed graph partitioning problems

Improved embeddings of graph metrics into random trees

Small hop-diameter sparse spanners for doubling metrics

On nash equilibria for a network creation game

Approximating unique games

Computing sequential equilibria for two-player games

A deterministic subexponential algorithm for solving parity games

Finding nucleolus of flow game

Predicting the "unpredictable"

A near-tight approximation lower bound and algorithm for the kidnapped robot problem

An asymptotic approximation algorithm for 3D-strip packing

Facility location with hierarchical facility costs

Combination can be hard: approximability of the unique coverage problem

Computing steiner minimum trees in Hamming metric

Robust shape fitting via peeling and grating coresets

Tightening non-simple paths and cycles on surfaces

Anisotropic surface meshing

Simultaneous diagonal flips in plane triangulations

Morphing orthogonal planar graph drawings

On the capacity of information networks

Lower bounds for asymmetric communication channels and distributed source coding

Self-improving algorithms

Cake cutting really is not a piece of cake

Testing triangle-freeness in general graphs

Constraint solving via fractional edge covers

Testing graph isomorphism

Efficient construction of unit circular-arc models

On the chromatic number of some geometric hypergraphs

A robust maximum completion time measure for scheduling

Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling

Improved approximation algorithms for broadcast scheduling

Distributed selfish load balancing

Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management

Rank/select operations on large alphabets: a tool for text indexing

O(log log n)-competitive dynamic binary search trees

The rainbow skip graph: a fault-tolerant constant-degree distributed data structure

Design of data structures for mergeable trees

Implicit dictionaries with O(1) modifications per update and fast search

Sampling binary contingency tables with a greedy start

Asymmetric balanced allocation with simple hash functions

Balanced allocation on graphs

Superiority and complexity of the spaced seeds

Solving random satisfiable 3CNF formulas in expected polynomial time

Analysis of incomplete data and an intrinsic-dimension Helly theorem

Finding large sticks and potatoes in polygons

Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting

Vertical ray shooting and computing depth orders for fat objects

On the number of plane graphs

All-pairs shortest paths for unweighted undirected graphs in o(mn) time

An O (n log n) algorithm for maximum st-flow in a directed planar graph

A simple GAP-canceling algorithm for the generalized maximum flow problem

Four point conditions and exponential neighborhoods for symmetric TSP

Upper degree-constrained partial orientations

On the tandem duplication-random loss model of genome rearrangement

Reducing tile complexity for self-assembly through temperature programming

Cache-oblivious string dictionaries

Cache-oblivious dynamic programming

A computational study of external-memory BFS algorithms

Tight approximation algorithms for maximum general assignment problems

Approximating the k-multicut problem

The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema

8/7-approximation algorithm for (1,2)-TSP

Improved lower and upper bounds for universal TSP in planar metrics

Leontief economies encode nonzero sum two-player games

Bottleneck links, variable demand, and the tragedy of the commons

The complexity of quantitative concurrent parity games

Equilibria for economies with production: constant-returns technologies and production planning constraints

Approximation algorithms for wavelet transform coding of data streams

Simpler algorithm for estimating frequency moments of data streams

Trading off space for passes in graph streaming problems

Maintaining significant stream statistics over sliding windows

Streaming and sublinear approximation of entropy and information distances

FPTAS for mixed-integer polynomial optimization with a fixed number of variables

Linear programming and unique sink orientations

Generating all vertices of a polyhedron is hard

A semidefinite programming approach to tensegrity theory and realizability of graphs

Ordering by weighted number of wins gives a good ranking for weighted tournaments

Weighted isotonic regression under the $L_{1}$ norm

Oblivious string embeddings and edit distance approximations

Spanners and emulators with sublinear distance errors

Certifying large branch-width

DAG-width: connectivity measure for directed graphs

On the diameter of Eulerian orientations of graphs

Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition

Subgraph characterization of red/blue-split graph and kőnig egerváry graphs

Critical chromatic number and the complexity of perfect packings in graphs

On the number of crossing-free matchings, (cycles, and partitions)

Slow mixing of glauber dynamics via topological obstructions

Quantum verification of matrix products

Counting without sampling: new algorithms for enumeration problems using statistical physics

Accelerating simulated annealing for the permanent and combinatorial counting problems

Query-efficient algorithms for polynomial interpolation over composites

New lower bounds for oblivious routing in undirected graphs

Anytime algorithms for multi-armed bandit problems

Robbing the bandit: less regret in online geometric optimization against an adaptive adversary

On the competitive ratio of evaluating priced functions

Randomized online algorithms for minimum metric bipartite matching

Analyzing BitTorrent and related peer-to-peer networks

Oblivious network design

The price of being near-sighted

Scalable leader election

Deterministic boundary recognition and topology extraction for large sensor networks

Improved lower bounds for embeddings into $L_{1}$

$l^{2}_{2}$ spreading metrics for vertex ordering problems

Trees and Markov convexity

An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing

A tight upper bound on the probabilistic embedding of series-parallel graphs

Single-value combinatorial auctions and implementation in undominated strategies

An improved approximation algorithm for combinatorial auctions with submodular bidders

Revenue maximization when bidders have budgets

Knapsack auctions

Single-minded unlimited supply pricing on sparse instances

The complexity of matrix completion

Relating singular values and discrepancy of weighted directed graphs

Matrix approximation and projective clustering via volume sampling

Sampling algorithms for $l_{2}$ regression and applications

The hunting of the bump: on maximizing statistical discrepancy

A general approach for incremental approximation and hierarchical clustering

The space complexity of pass-efficient algorithms for clustering

Correlation clustering with a fixed number of clusters

On k-Median clustering in high dimensions

Entropy based nearest neighbor search in high dimensions

A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries

Efficient algorithms for substring near neighbor problem

Many distances in planar graphs

Pattern matching with address errors: rearrangement distances

Squeezing succinct data structures into entropy bounds

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in