:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Kintali, Shiva, Kothari, Nishad, Kumar, Akash
Format:	Preprint
Published:	2011
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/1107.4824
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Width Parameters for Minimum Flow Decomposition
by: Grigorjew, Andreas, et al.
Published: (2024)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
by: Lanzinger, Matthias, et al.
Published: (2023)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
by: Arhire, Andrei, et al.
Published: (2025)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Fully Dynamic Strongly Connected Components in Planar Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Integer and Unsplittable Multiflows in Series-Parallel Digraphs
by: Almoghrabi, Mohammed Majthoub, et al.
Published: (2024)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

The Impact of Approximation on Algorithmic Progress
by: Li, Jeffery, et al.
Published: (2026)

Upward Book Embeddings of Partitioned Digraphs
by: Da Lozzo, Giordano, et al.
Published: (2026)

Counting Patterns in Degenerate Graphs in Constant Space
by: Komarath, Balagopal, et al.
Published: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Approximation Algorithms for Fair Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2025)

Towards Transitive-free Digraphs
by: Abhinav, Ankit, et al.
Published: (2025)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Twin-Width Meets Feedback Edges and Vertex Integrity
by: Balabán, Jakub, et al.
Published: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

Greedy BST on Permutation Initial Tree
by: Pareek, Akash
Published: (2024)

Finding Induced Subgraphs from Graphs with Small Mim-Width
by: Otachi, Yota, et al.
Published: (2024)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
by: Armbruster, Alexander, et al.
Published: (2026)

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
by: Zhang, Guangyi, et al.
Published: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
by: Soma, Tasuku, et al.
Published: (2025)