Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GRAPH THEORY:
Reports tagged with Graph Theory:
TR96-016 | 6th February 1996
Andrea E. F. Clementi, Luca Trevisan

Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

We provide new non-approximability results for the restrictions
of the min-VC problem to bounded-degree, sparse and dense graphs.
We show that for a sufficiently large B, the recent 16/15 lower
bound proved by Bellare et al. extends with negligible
loss to graphs with bounded ... more >>>


TR97-040 | 17th September 1997
Dorit Dor, Shay Halperin, Uri Zwick

All Pairs Almost Shortest Paths

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple
argument shows that computing all distances in G with an additive
one-sided error of at most 1 is as hard as Boolean matrix
multiplication. Building on recent work of Aingworth, Chekuri and
Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time
more >>>


TR16-017 | 24th December 2015
Georgios Stamoulis

Limitations of Linear Programming Techniques for Bounded Color Matchings

Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions ... more >>>


TR17-033 | 19th February 2017
Daniel Kane, Shachar Lovett, Sankeerth Rao

Labeling the complete bipartite graph with no zero cycles

Revisions: 2

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... more >>>




ISSN 1433-8092 | Imprint