M. Goldberg

activity

19942026

most citedTracking and Predicting Evolution of Social Communities

32 citations · 33 across the 7 of their papers we have counts for

collaborators

Showing math.COShow all

5 papers · 1 filter

math.CO2017

A conditional greedy algorithm for edge-coloring

Mark K. Goldberg

We present a novel algorithm for edge-coloring of multigraphs. The correctness of this algorithm for multigraphs with $χ^{'} > Δ + 1$ ( $χ^{'}$ is the chromatic edge number and $Δ$ is the m…

math.CO2016

On degree-colorings of multigraphs

Mark K. Goldberg

A notion of degree-coloring is introduced; it captures some, but not all properties of standard edge-coloring. We conjecture that the smallest number of colors needed for degree-co…

math.CO2010

Embedding a Forest in a Graph

Mark Goldberg, Malik Magdon-Ismail

For \math{p\ge 1}, we prove that every forest with \math{p} trees whose sizes are $a_{1}, ..., a_{p}$ can be embedded in any graph containing at least $\sum_{i = 1}^{p} (a_{i} + 1)$ vertices…

math.CO1995

Path optimization and near-greedy analysis for graph partitioning: an empirical study

Jonathan Berry, Mark Goldberg

This paper presents the results of an experimental study of graph partitioning. We describe a new heuristic technique, path optimization, and its application to two variations of g…

math.CO1994

Inverting sets and the packing problem

Vance Faber, Mark Goldberg, Emanuel Knill +1

Given a set $V$ , a subset $S$ , and a permutation $π$ of $V$ , we say that $π$ permutes $S$ if $π (S) \cap S = \emptyset$ . Given a collection $\cS = \{V; S_1,\ldots , S_m\}$, where $S…