Zobrazeno 1 - 10
of 44
pro vyhledávání: '"S. L. Hakimi"'
Publikováno v:
Networks. 34:250-257
We begin by examining the dynamic behavior of a facility location such as a 1-median or a 1-center on a network when the parameters of the network are known functions of time. The parameters of the network include the lengths of the edges and the dem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::484538b9eef97f852127702fb7e58620
https://doi.org/10.1002/(sici)1097-0037(199912)34:4<250::aid-net3>3.0.co
https://doi.org/10.1002/(sici)1097-0037(199912)34:4<250::aid-net3>3.0.co
Publikováno v:
Scopus-Elsevier
Information Processing Letters, vol 63, iss 5
Information Processing Letters, vol 63, iss 5
It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the problem of orienting a connected graph with cut edges in order to maximize the number of ordered vertex pairs (x
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::327e1ccc9b1a44f0aef587b272116785
https://doi.org/10.1016/s0020-0190(97)00129-4
https://doi.org/10.1016/s0020-0190(97)00129-4
Publikováno v:
Journal of Graph Theory. 20:177-194
A graph G is degree-bounded-colorable (briefly, db-colorable) if it can be properly vertex-colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::31935be746f31b060d5d111a12bd216c
https://doi.org/10.1002/jgt.3190200207
https://doi.org/10.1002/jgt.3190200207
Publikováno v:
SIAM Journal on Computing. 23:355-372
Each vertex of an undirected graph possesses a piece of information that must be sent to every other vertex. They communicate by sending bounded size packets of messages from one vertex to another. The authors describe parallel algorithms, which acco
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::89720c6b444bd224052176baf62fc66d
https://doi.org/10.1137/s0097539790192672
https://doi.org/10.1137/s0097539790192672
Publikováno v:
SIAM Journal on Discrete Mathematics. 6:565-574
This paper considers the following problem: Given a positive integer t and graph H, construct a graph G from H by adding a minimum number $\Delta ( t,H )$ (respectively, $\Delta ' ( t,H )$) of edges and an appropriate number of vertices, such that af
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2683747c713ea0e2132c4efe4ce5a40f
https://doi.org/10.1137/0406044
https://doi.org/10.1137/0406044
Publikováno v:
Networks. 23:543-555
The study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (≥1) such facilities. We will consid
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8f499beff75ca34112fbf0f7faffc4d4
https://doi.org/10.1002/net.3230230605
https://doi.org/10.1002/net.3230230605
Publikováno v:
IEEE Transactions on Computers. 42:253-256
Consider a network in which each unit initially knows only its own identity and the identity of its immediate neighbors. Suppose each unit has a message intended for all other units. The authors give a distributed algorithm to accomplish this in poin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::83acb4bc4fb9be92960cc56ca3c08e0d
https://doi.org/10.1109/12.204799
https://doi.org/10.1109/12.204799
Publikováno v:
Networks. 22:317-333
Consider a network consisting of units and links that connect pairs of units. Suppose each of the units possesses a unique message that is to be received by all other units. This is called gossiping. A related problem is that of census taking in whic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e266a2f576cb5032fdf90969d4d51115
https://doi.org/10.1002/net.3230220402
https://doi.org/10.1002/net.3230220402
Autor:
E. F. Schmeichel, S. L. Hakimi
Publikováno v:
CVGIP: Graphical Models and Image Processing. 53:132-136
Given a set of points S = {(x1, y1), (x2, y2), …, (xN, yN)} in R2 with x1 < x2 < … < xN, we want to construct a polygonal (i.e., continuous, piecewise linear) function f with a small number of corners (i.e., nondifferentiable points) which fits S
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::592df83757b8723790079a3862c60084
https://doi.org/10.1016/1049-9652(91)90056-p
https://doi.org/10.1016/1049-9652(91)90056-p
Publikováno v:
Discrete Applied Mathematics. 28:191-195
We show that recognizing 1-tough graphs is NP-hard, thereby settling a long-standing open problem. We also prove it is NP-hard to recognize t-tough graphs for any fixed positive rational number t.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::128cc7365c0396442bc47bb31d949d32
https://doi.org/10.1016/0166-218x(90)90001-s
https://doi.org/10.1016/0166-218x(90)90001-s