4 papers
Optimized Degree Realization: Minimum Dominating Set & Maximum Matching
Amotz Bar-Noy, Igor Kalinichev, David Peleg +1
The Degree Realization problem requires, given a sequence of positive integers, to decide whether there exists a graph whose degrees correspond to , and to construct suc…
Degree Realization by Bipartite Cactus Graphs
Amotz Bar-Noy, Toni Bohnlein, David Peleg +2
The \textsc{Degree Realization} problem with respect to a graph family is defined as follows. The input is a sequence of positive integers, and the goal is to…
Degree Realization by Bipartite Multigraphs
Amotz Bar-Noy, Toni Bohnlein, David Peleg +1
The problem of realizing a given degree sequence by a multigraph can be thought of as a relaxation of the classical degree realization problem (where the realizing graph is simple)…
Approximate Realizations for Outerplanaric Degree Sequences
Amotz Bar-Noy, Toni Bohnlein, David Peleg +2
We study the question of whether a sequence d = (d_1,d_2, \ldots, d_n) of positive integers is the degree sequence of some outerplanar (a.k.a. 1-page book embeddable) graph G. If s…