Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-02-17

AUTHORS

Bhaskar Das Gupta, Marek Karpinski, Nasim Mobasheri, Farzane Yahyanejad

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
  • 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: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "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", 
            "givenName": "Bhaskar", 
            "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"
            }, 
            "familyName": "Yahyanejad", 
            "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", 
            "volumeNumber": "80"
          }
        ], 
        "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s00453-017-0291-7 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nceadf4d733e548cea099e30262c66ff9
    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
    73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    74 schema:sdPublisher N1a55b3a1ed694e1daeab384e089268e0
    75 schema:url https://doi.org/10.1007/s00453-017-0291-7
    76 sgo:license sg:explorer/license/
    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
    86 schema:givenName Bhaskar
    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
    92 N99626788d8a84506910b91daa1045178 schema:volumeNumber 80
    93 rdf:type schema:PublicationVolume
    94 Nceadf4d733e548cea099e30262c66ff9 rdf:first N3059c22f676e47cab60edeb034c28080
    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
    122 schema:familyName Yahyanejad
    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
     




    Preview window. Press ESC to close (or click here)


    ...