# Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2017-02-17

AUTHORS

ABSTRACT

δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}-Hyperbolic graphs, originally conceived by Gromov (Essays in group theory. 1987), occur often in many network applications; for fixed δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of “non-expander” graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} on expansion and cut-size bounds on graphs (here δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} need not be a constant), and the asymptotic ranges of δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}-hyperbolic graphs as a function of δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s–t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}-hyperbolic graphs (whereδ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}is a functionfof the number of nodes, the exact nature of growth of f being dependent on the particular problem considered). More... »

PAGES

772-800

### References to SciGraph publications

• 2014-08-29. The Minimum Vulnerability Problem in ALGORITHMICA
• 2005. Distance Labeling in Hyperbolic Graphs in ALGORITHMS AND COMPUTATION
• 2012-02-24. Finding paths with minimum shared edges in JOURNAL OF COMBINATORIAL OPTIMIZATION
• 1988. Dynamic programming on graphs with bounded treewidth in AUTOMATA, LANGUAGES AND PROGRAMMING
• 1998-12. Expanders are not hyperbolic in ISRAEL JOURNAL OF MATHEMATICS
• 1999. Metric Spaces of Non-Positive Curvature in NONE
• 2009-01-18. Curvature of Indoor Sensor Network: Clustering Coefficient in EURASIP JOURNAL ON WIRELESS COMMUNICATIONS AND NETWORKING
• 2007. Packing and Covering δ-Hyperbolic Spaces by Balls in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
• 2010-12-24. Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs in ALGORITHMICA
• 2012-05-29. Finite Transitive Graph Embeddings into a Hyperbolic Metric Space Must Stretch or Squeeze in GEOMETRIC ASPECTS OF FUNCTIONAL ANALYSIS
• 1987. Hyperbolic Groups in ESSAYS IN GROUP THEORY

TITLE

Algorithmica

ISSUE

2

VOLUME

80

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-017-0291-7

DOI

http://dx.doi.org/10.1007/s00453-017-0291-7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1083911729

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA",
"id": "http://www.grid.ac/institutes/grid.185648.6",
"name": [
"Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
],
"type": "Organization"
},
"familyName": "Das Gupta",
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Bonn, 53113, Bonn, Germany",
"id": "http://www.grid.ac/institutes/grid.10388.32",
"name": [
"Department of Computer Science, University of Bonn, 53113, Bonn, Germany"
],
"type": "Organization"
},
"familyName": "Karpinski",
"givenName": "Marek",
"id": "sg:person.011636042271.02",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA",
"id": "http://www.grid.ac/institutes/grid.185648.6",
"name": [
"Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
],
"type": "Organization"
},
"familyName": "Mobasheri",
"givenName": "Nasim",
"id": "sg:person.01325505356.23",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01325505356.23"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA",
"id": "http://www.grid.ac/institutes/grid.185648.6",
"name": [
"Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA"
],
"type": "Organization"
},
"givenName": "Farzane",
"id": "sg:person.012577157437.32",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012577157437.32"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-19488-6_110",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041426675",
"https://doi.org/10.1007/3-540-19488-6_110"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02783040",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034381686",
"https://doi.org/10.1007/bf02783040"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1155/2008/213185",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014245856",
"https://doi.org/10.1155/2008/213185"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-010-9478-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047593355",
"https://doi.org/10.1007/s00453-010-9478-x"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74208-1_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032702066",
"https://doi.org/10.1007/978-3-540-74208-1_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10878-012-9462-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003532968",
"https://doi.org/10.1007/s10878-012-9462-2"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-014-9927-z",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027251872",
"https://doi.org/10.1007/s00453-014-9927-z"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-662-12494-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018384993",
"https://doi.org/10.1007/978-3-662-12494-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-29849-3_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051462140",
"https://doi.org/10.1007/978-3-642-29849-3_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4613-9586-7_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038753055",
"https://doi.org/10.1007/978-1-4613-9586-7_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11602613_106",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026406190",
"https://doi.org/10.1007/11602613_106"
],
"type": "CreativeWork"
}
],
"datePublished": "2017-02-17",
"datePublishedReg": "2017-02-17",
"description": "Abstract\u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document}-Hyperbolic graphs, originally conceived by Gromov (Essays in group theory. 1987), occur often in many network applications; for fixed \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document}, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of \u201cnon-expander\u201d graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document} on expansion and cut-size bounds on graphs (here \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document} need not be a constant), and the asymptotic ranges of \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document} for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document}-hyperbolic graphs as a function of \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document}, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s\u2013t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for \u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document}-hyperbolic graphs (where\u03b4\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\delta$$\\end{document}is a functionfof the number of nodes, the exact nature of growth of f being dependent on the particular problem considered).",
"genre": "article",
"id": "sg:pub.10.1007/s00453-017-0291-7",
"isAccessibleForFree": true,
"isFundedItemOf": [
{
"id": "sg:grant.3135580",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"hyperbolic graphs",
"constructive bounds",
"related combinatorial problems",
"improved approximation algorithms",
"asymptotic range",
"algorithmic consequences",
"combinatorial problems",
"algorithmic implications",
"such graphs",
"approximation algorithm",
"bounds",
"graph",
"t cut",
"proof technique",
"interesting class",
"main motivation",
"network applications",
"such expansion",
"Gromov",
"problem",
"expansion",
"small number",
"algorithm",
"class",
"parameters",
"applications",
"node expansion",
"function",
"large family",
"number",
"technique",
"cut",
"results",
"effect",
"range",
"measures",
"family",
"consequences",
"motivation",
"knowledge",
"witness",
"implications",
"paper"
],
"name": "Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications",
"pagination": "772-800",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1083911729"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-017-0291-7"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-017-0291-7",
"https://app.dimensions.ai/details/publication/pub.1083911729"
],
"sdDataset": "articles",
"sdDatePublished": "2022-11-24T21:02",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_749.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-017-0291-7"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0291-7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0291-7'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0291-7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0291-7'

This table displays all metadata directly associated to this object as RDF triples.

169 TRIPLES      21 PREDICATES      78 URIs      59 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
4 schema:citation sg:pub.10.1007/11602613_106
5 sg:pub.10.1007/3-540-19488-6_110
6 sg:pub.10.1007/978-1-4613-9586-7_3
7 sg:pub.10.1007/978-3-540-74208-1_5
8 sg:pub.10.1007/978-3-642-29849-3_5
9 sg:pub.10.1007/978-3-662-12494-9
10 sg:pub.10.1007/bf02783040
11 sg:pub.10.1007/s00453-010-9478-x
12 sg:pub.10.1007/s00453-014-9927-z
13 sg:pub.10.1007/s10878-012-9462-2
14 sg:pub.10.1155/2008/213185
15 schema:datePublished 2017-02-17
16 schema:datePublishedReg 2017-02-17
17 schema:description Abstractδ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}-Hyperbolic graphs, originally conceived by Gromov (Essays in group theory. 1987), occur often in many network applications; for fixed δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of “non-expander” graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} on expansion and cut-size bounds on graphs (here δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} need not be a constant), and the asymptotic ranges of δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}-hyperbolic graphs as a function of δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s–t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}-hyperbolic graphs (whereδ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document}is a functionfof the number of nodes, the exact nature of growth of f being dependent on the particular problem considered).
18 schema:genre article
19 schema:isAccessibleForFree true
20 schema:isPartOf N99626788d8a84506910b91daa1045178
21 Nd5b4aa896ec848ee9bd417e31b4c362a
22 sg:journal.1047644
23 schema:keywords Gromov
24 algorithm
25 algorithmic consequences
26 algorithmic implications
27 applications
28 approximation algorithm
29 asymptotic range
30 bounds
31 class
32 combinatorial problems
33 consequences
34 constructive bounds
35 cut
36 effect
37 expansion
38 family
39 function
40 graph
41 hyperbolic graphs
42 implications
43 improved approximation algorithms
44 interesting class
45 knowledge
46 large family
47 main motivation
48 measures
49 motivation
50 network applications
51 node expansion
52 number
53 paper
54 parameters
55 problem
56 proof technique
57 range
58 related combinatorial problems
59 results
60 small number
61 such expansion
62 such graphs
63 t cut
64 technique
65 witness
66 schema:name Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
67 schema:pagination 772-800
68 schema:productId N2ed354ac7eb94b95aacbd361a629294b
69 Nfb68fb687b2c41cbaefd9a936642f895
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083911729
71 https://doi.org/10.1007/s00453-017-0291-7
72 schema:sdDatePublished 2022-11-24T21:02
74 schema:sdPublisher N1a55b3a1ed694e1daeab384e089268e0
75 schema:url https://doi.org/10.1007/s00453-017-0291-7
77 sgo:sdDataset articles
78 rdf:type schema:ScholarlyArticle
79 N1a55b3a1ed694e1daeab384e089268e0 schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N2ed354ac7eb94b95aacbd361a629294b schema:name dimensions_id
82 schema:value pub.1083911729
83 rdf:type schema:PropertyValue
84 N3059c22f676e47cab60edeb034c28080 schema:affiliation grid-institutes:grid.185648.6
85 schema:familyName Das Gupta
87 rdf:type schema:Person
88 N5cfdc2c58d7940999a47a7b12debdbba rdf:first sg:person.011636042271.02
89 rdf:rest Nfc323c4c769d47cd83b7f027b0438018
90 N965cf81c0b4149b5bed8a3bea942987e rdf:first sg:person.012577157437.32
91 rdf:rest rdf:nil
93 rdf:type schema:PublicationVolume
95 rdf:rest N5cfdc2c58d7940999a47a7b12debdbba
96 Nd5b4aa896ec848ee9bd417e31b4c362a schema:issueNumber 2
97 rdf:type schema:PublicationIssue
98 Nfb68fb687b2c41cbaefd9a936642f895 schema:name doi
99 schema:value 10.1007/s00453-017-0291-7
100 rdf:type schema:PropertyValue
101 Nfc323c4c769d47cd83b7f027b0438018 rdf:first sg:person.01325505356.23
102 rdf:rest N965cf81c0b4149b5bed8a3bea942987e
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
107 schema:name Computation Theory and Mathematics
108 rdf:type schema:DefinedTerm
109 sg:grant.3135580 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-017-0291-7
110 rdf:type schema:MonetaryGrant
111 sg:journal.1047644 schema:issn 0178-4617
112 1432-0541
113 schema:name Algorithmica
114 schema:publisher Springer Nature
115 rdf:type schema:Periodical
116 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
117 schema:familyName Karpinski
118 schema:givenName Marek
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
120 rdf:type schema:Person
121 sg:person.012577157437.32 schema:affiliation grid-institutes:grid.185648.6
123 schema:givenName Farzane
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012577157437.32
125 rdf:type schema:Person
126 sg:person.01325505356.23 schema:affiliation grid-institutes:grid.185648.6
127 schema:familyName Mobasheri
128 schema:givenName Nasim
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01325505356.23
130 rdf:type schema:Person
131 sg:pub.10.1007/11602613_106 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026406190
132 https://doi.org/10.1007/11602613_106
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/3-540-19488-6_110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041426675
135 https://doi.org/10.1007/3-540-19488-6_110
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/978-1-4613-9586-7_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038753055
138 https://doi.org/10.1007/978-1-4613-9586-7_3
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/978-3-540-74208-1_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032702066
141 https://doi.org/10.1007/978-3-540-74208-1_5
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/978-3-642-29849-3_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051462140
144 https://doi.org/10.1007/978-3-642-29849-3_5
145 rdf:type schema:CreativeWork
146 sg:pub.10.1007/978-3-662-12494-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018384993
147 https://doi.org/10.1007/978-3-662-12494-9
148 rdf:type schema:CreativeWork
149 sg:pub.10.1007/bf02783040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034381686
150 https://doi.org/10.1007/bf02783040
151 rdf:type schema:CreativeWork
152 sg:pub.10.1007/s00453-010-9478-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1047593355
153 https://doi.org/10.1007/s00453-010-9478-x
154 rdf:type schema:CreativeWork
155 sg:pub.10.1007/s00453-014-9927-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1027251872
156 https://doi.org/10.1007/s00453-014-9927-z
157 rdf:type schema:CreativeWork
158 sg:pub.10.1007/s10878-012-9462-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003532968
159 https://doi.org/10.1007/s10878-012-9462-2
160 rdf:type schema:CreativeWork
161 sg:pub.10.1155/2008/213185 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014245856
162 https://doi.org/10.1155/2008/213185
163 rdf:type schema:CreativeWork
164 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, 53113, Bonn, Germany
165 schema:name Department of Computer Science, University of Bonn, 53113, Bonn, Germany
166 rdf:type schema:Organization
167 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA
168 schema:name Department of Computer Science, University of Illinois at Chicago, 60607, Chicago, IL, USA
169 rdf:type schema:Organization