-
Chapter and Conference Paper
Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs
In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters – maximum independent set, minimum dominating set and maximum matching – on sparse graph classes, i.e....
-
Chapter and Conference Paper
A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
Given a graph G and a set \(\mathcal {T}=\big \{ (s_i, t_i) : 1\le i\le k \big \}\) ...
-
Article
Open AccessA Tight Lower Bound for Planar Steiner Orientation
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs ...
-
Chapter and Conference Paper
Algorithms and Hardness Results for Nearest Neighbor Problems in Bicolored Point Sets
In the context of computational supervised learning, the primary objective is the classification of data. Especially, the goal is to provide the system with “training” data and design a method which uses the t...
-
Chapter and Conference Paper
A Tight Lower Bound for Steiner Orientation
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs ...
-
Chapter and Conference Paper
Can We Create Large k-Cores by Adding Few Edges?
The notion of a k-core, defined by Seidman [’83], has turned out to be useful in analyzing network structures. The k-core of a given simple and undirected graph is the maximal induced subgraph such that each vert...
-
Article
List H-Coloring a Graph by Removing Few Vertices
In the deletion version of the list homomorphism problem, we are given graphs G and H, a list \(L(v)\subseteq V(H)\) ...
-
Article
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands
Given an edge-weighted directed graph \(G=(V,E)\) ...
-
Reference Work Entry In depth
Shadowless Solutions for Fixed-Parameter Tractability of Directed Graphs
-
Chapter and Conference Paper
Tight Bounds for Gomory-Hu-like Cut Counting
By a classical result of Gomory and Hu (1961), in every edge-weighted graph \(G=(V,E,w)\) , the minimum st-cut values,...
-
Living Reference Work Entry In depth
Shadowless Solutions for Fixed-Parameter Tractability of Directed Graphs
-
Article
On the SIG-Dimension of Trees Under the L ∞-Metric
Let \({{\mathcal P},}\) where $${|{\mat...
-
Chapter and Conference Paper
Fixed-Parameter and Approximation Algorithms: A New Look
A Fixed-Parameter Tractable (FPT) ρ-approximation algorithm for a minimization (resp. maximization) parameterized problem P is an FPT algorithm that, given an instance (x, k) ∈ P computes a solution of cost at mo...
-
Chapter and Conference Paper
Faster Exact Algorithms for Some Terminal Set Problems
Many problems on graphs can be expressed in the following language: given a graph G = (V,E) and a terminal set T ⊆ V, find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) pass...
-
Chapter and Conference Paper
List H-Coloring a Graph by Removing Few Vertices
In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) ⊆ V(H) for each vertex v ∈ V(G), and an integer k. The task is to decide whether there exists a set W ⊆ V(G) of s...
-
Chapter and Conference Paper
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Given a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. Bodlaender (WG ’91) gave the first fixed-parameter algo...
-
Chapter and Conference Paper
Parameterized Algorithms for Boxicity
In this paper we initiate an algorithmic study of Boxicity, a combinatorially well studied graph invariant, from the viewpoint of parameterized algorithms. The boxicity of an arbitrary graph G with the vertex set...
