Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Yahav Nussbaum"'
Autor:
Andrew R. Curtis, Min Chih Lin, Ross M. Mcconnell, Yahav Nussbaum, Francisco Juan Soulignac, Jeremy P. Spinrad, Jayme Luiz Szwarcfiter
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 15 no. 1, Iss Discrete Algorithms (2013)
Discrete Algorithms
Externí odkaz:
https://doaj.org/article/2f380f2e29a6498995ad74be00848e47
Publikováno v:
ACM Transactions on Algorithms. 13:1-42
We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O ( n log
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::02079c3c9e96622e054d0fd03236ffcc
https://doi.org/10.1145/3039873
https://doi.org/10.1145/3039873
Publikováno v:
FOCS
We give an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b106642e8623a0f12486e41f8c5f3edd
https://doi.org/10.1137/15m1042929
https://doi.org/10.1137/15m1042929
Autor:
Yahav Nussbaum
Publikováno v:
Discrete Applied Mathematics. 167:228-238
In a partitioned probe graph the vertex set is partitioned into probes and non-probes, such that the set of non-probes is an independent set. A probe proper interval graph is the intersection graph of a set of intervals on the line such that every ve
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::77dec29bbcde6c37d103504c05fb2182
https://doi.org/10.1016/j.dam.2013.11.013
https://doi.org/10.1016/j.dam.2013.11.013
Autor:
Yahav Nussbaum, Haim Kaplan
Publikováno v:
Algorithmica. 61:694-737
We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad (Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 128–137, 1993) and Eschen (PhD thesis, 1997). O
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5c2f840ddd0ba89149f58daea9a0c1ae
https://doi.org/10.1007/s00453-010-9432-y
https://doi.org/10.1007/s00453-010-9432-y
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::52b301aace5f7c1c4ecd20a4de755908
http://arxiv.org/abs/1404.0977
http://arxiv.org/abs/1404.0977
Autor:
Yahav Nussbaum, Ross M. McConnell, Andrew R. Curtis, Jeremy P. Spinrad, Min Chih Lin, Jayme Luiz Szwarcfiter, Francisco J. Soulignac
Publikováno v:
CONICET Digital (CONICET)
Consejo Nacional de Investigaciones Científicas y Técnicas
instacron:CONICET
Discrete Mathematics and Theoretical Computer Science
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.157--182
Consejo Nacional de Investigaciones Científicas y Técnicas
instacron:CONICET
Discrete Mathematics and Theoretical Computer Science
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.157--182
Discrete Algorithms
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but wor
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but wor
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ffabf03f42b3ebb5da7ca40052dac8f8
https://doi.org/10.46298/dmtcs.625
https://doi.org/10.46298/dmtcs.625
Publikováno v:
FOCS
Let G = (V,E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t in V\{s}. We show how to solve this problem in near-linear O(n log^3 n) time. Previously, no better solution wa
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30568dfa9f2b02dc0af5c2c6102f639b
Publikováno v:
STOC
We study the min st-cut and max st-flow problems in planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph and two vertices s and t computes a min st-cut in O(n log log n) time. Sec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1655eee2e2d39157ae5f3fee3761e57a
https://doi.org/10.1145/1993636.1993679
https://doi.org/10.1145/1993636.1993679