Fair Matchings and Related Problems View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-04-08

AUTHORS

Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail

ABSTRACT

Let G=(A∪B,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (A \cup B, E)$$\end{document} be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document} be the worst rank used. A matching M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} is fair in G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} if it has maximum cardinality, subject to this, M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} matches the minimum number of vertices to rank r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document} neighbors, subject to that, M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} matches the minimum number of vertices to rank (r-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(r-1)$$\end{document} neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation—this can be of independent interest. More... »

PAGES

1184-1203

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-015-9994-9

DOI

http://dx.doi.org/10.1007/s00453-015-9994-9

DIMENSIONS

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


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": "Chalmers University of Technology, Gothenburg, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.5371.0", 
          "name": [
            "Chalmers University of Technology, Gothenburg, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Huang", 
        "givenName": "Chien-Chung", 
        "id": "sg:person.012535026361.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012535026361.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tata Institute of Fundamental Research, Mumbai, India", 
          "id": "http://www.grid.ac/institutes/grid.22401.35", 
          "name": [
            "Tata Institute of Fundamental Research, Mumbai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kavitha", 
        "givenName": "Telikepalli", 
        "id": "sg:person.015551052213.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015551052213.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Harokopio University, Athens, Greece", 
          "id": "http://www.grid.ac/institutes/grid.15823.3d", 
          "name": [
            "Harokopio University, Athens, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Michail", 
        "givenName": "Dimitrios", 
        "id": "sg:person.07510643303.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07510643303.39"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01586040", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036065665", 
          "https://doi.org/10.1007/bf01586040"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11561071_68", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052125187", 
          "https://doi.org/10.1007/11561071_68"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11940128_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035181761", 
          "https://doi.org/10.1007/11940128_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-38233-8_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012548769", 
          "https://doi.org/10.1007/978-3-642-38233-8_27"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2015-04-08", 
    "datePublishedReg": "2015-04-08", 
    "description": "Let G=(A\u222aB,E)\\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}$$G = (A \\cup B, E)$$\\end{document} be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r\\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}$$r$$\\end{document} be the worst rank used. A matching M\\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}$$M$$\\end{document} is fair in G\\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}$$G$$\\end{document} if it has maximum cardinality, subject to this, M\\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}$$M$$\\end{document} matches the minimum number of vertices to rank\u00a0r\\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}$$r$$\\end{document} neighbors, subject to that, M\\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}$$M$$\\end{document} matches the minimum number of vertices to rank\u00a0(r-1)\\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}$$(r-1)$$\\end{document} neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G\\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}$$G$$\\end{document}. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation\u2014this can be of independent interest.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-015-9994-9", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "74"
      }
    ], 
    "keywords": [
      "combinatorial algorithm", 
      "single-source shortest path computations", 
      "bipartite graphs", 
      "efficient combinatorial algorithm", 
      "vertex cover problem", 
      "minimum number", 
      "shortest path computation", 
      "fair matching", 
      "LP duality", 
      "independent interest", 
      "maximum cardinality", 
      "cover problem", 
      "matching problem", 
      "path computation", 
      "vertices", 
      "related problems", 
      "graph", 
      "algorithm", 
      "problem", 
      "duality", 
      "neighbors", 
      "computation", 
      "cardinality", 
      "scaling", 
      "order of preference", 
      "matching", 
      "rank", 
      "number", 
      "version", 
      "order", 
      "worst rank", 
      "interest", 
      "preferences"
    ], 
    "name": "Fair Matchings and Related Problems", 
    "pagination": "1184-1203", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026774630"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-015-9994-9"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-015-9994-9", 
      "https://app.dimensions.ai/details/publication/pub.1026774630"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T20:59", 
    "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_653.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-015-9994-9"
  }
]
 

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-015-9994-9'

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-015-9994-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-9994-9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-9994-9'


 

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

136 TRIPLES      21 PREDICATES      61 URIs      49 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-015-9994-9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ndfc5428571ca4b5889c53421e6b45098
4 schema:citation sg:pub.10.1007/11561071_68
5 sg:pub.10.1007/11940128_17
6 sg:pub.10.1007/978-3-642-38233-8_27
7 sg:pub.10.1007/bf01586040
8 schema:datePublished 2015-04-08
9 schema:datePublishedReg 2015-04-08
10 schema:description Let G=(A∪B,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (A \cup B, E)$$\end{document} be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document} be the worst rank used. A matching M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} is fair in G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} if it has maximum cardinality, subject to this, M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} matches the minimum number of vertices to rank r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document} neighbors, subject to that, M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} matches the minimum number of vertices to rank (r-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(r-1)$$\end{document} neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation—this can be of independent interest.
11 schema:genre article
12 schema:isAccessibleForFree true
13 schema:isPartOf N447a361205f7411289c80b0eb202bb37
14 Nc8eea11cef1145468a734e9471bf2d32
15 sg:journal.1047644
16 schema:keywords LP duality
17 algorithm
18 bipartite graphs
19 cardinality
20 combinatorial algorithm
21 computation
22 cover problem
23 duality
24 efficient combinatorial algorithm
25 fair matching
26 graph
27 independent interest
28 interest
29 matching
30 matching problem
31 maximum cardinality
32 minimum number
33 neighbors
34 number
35 order
36 order of preference
37 path computation
38 preferences
39 problem
40 rank
41 related problems
42 scaling
43 shortest path computation
44 single-source shortest path computations
45 version
46 vertex cover problem
47 vertices
48 worst rank
49 schema:name Fair Matchings and Related Problems
50 schema:pagination 1184-1203
51 schema:productId N74eb58d19f28409eae4b612d70094a05
52 Ne066bb8d0ef0492d912f4fbc1ba2f744
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026774630
54 https://doi.org/10.1007/s00453-015-9994-9
55 schema:sdDatePublished 2022-11-24T20:59
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Necc4a39cacb64a06accb6d8a1a3b6aff
58 schema:url https://doi.org/10.1007/s00453-015-9994-9
59 sgo:license sg:explorer/license/
60 sgo:sdDataset articles
61 rdf:type schema:ScholarlyArticle
62 N447a361205f7411289c80b0eb202bb37 schema:volumeNumber 74
63 rdf:type schema:PublicationVolume
64 N6af4c68f2af04b8eb036a6b037168d5d rdf:first sg:person.07510643303.39
65 rdf:rest rdf:nil
66 N74eb58d19f28409eae4b612d70094a05 schema:name doi
67 schema:value 10.1007/s00453-015-9994-9
68 rdf:type schema:PropertyValue
69 Nc8eea11cef1145468a734e9471bf2d32 schema:issueNumber 3
70 rdf:type schema:PublicationIssue
71 Ncdc87dc6831c48ae9e82e35049f96f27 rdf:first sg:person.015551052213.83
72 rdf:rest Ne969952e37ee49148e7c8c1d42e03bc4
73 Ndfc5428571ca4b5889c53421e6b45098 rdf:first sg:person.012535026361.26
74 rdf:rest Ncdc87dc6831c48ae9e82e35049f96f27
75 Ne066bb8d0ef0492d912f4fbc1ba2f744 schema:name dimensions_id
76 schema:value pub.1026774630
77 rdf:type schema:PropertyValue
78 Ne969952e37ee49148e7c8c1d42e03bc4 rdf:first sg:person.011757371347.43
79 rdf:rest N6af4c68f2af04b8eb036a6b037168d5d
80 Necc4a39cacb64a06accb6d8a1a3b6aff schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 sg:journal.1047644 schema:issn 0178-4617
89 1432-0541
90 schema:name Algorithmica
91 schema:publisher Springer Nature
92 rdf:type schema:Periodical
93 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
94 schema:familyName Mehlhorn
95 schema:givenName Kurt
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
97 rdf:type schema:Person
98 sg:person.012535026361.26 schema:affiliation grid-institutes:grid.5371.0
99 schema:familyName Huang
100 schema:givenName Chien-Chung
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012535026361.26
102 rdf:type schema:Person
103 sg:person.015551052213.83 schema:affiliation grid-institutes:grid.22401.35
104 schema:familyName Kavitha
105 schema:givenName Telikepalli
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015551052213.83
107 rdf:type schema:Person
108 sg:person.07510643303.39 schema:affiliation grid-institutes:grid.15823.3d
109 schema:familyName Michail
110 schema:givenName Dimitrios
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07510643303.39
112 rdf:type schema:Person
113 sg:pub.10.1007/11561071_68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052125187
114 https://doi.org/10.1007/11561071_68
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/11940128_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035181761
117 https://doi.org/10.1007/11940128_17
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/978-3-642-38233-8_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012548769
120 https://doi.org/10.1007/978-3-642-38233-8_27
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/bf01586040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036065665
123 https://doi.org/10.1007/bf01586040
124 rdf:type schema:CreativeWork
125 grid-institutes:grid.15823.3d schema:alternateName Harokopio University, Athens, Greece
126 schema:name Harokopio University, Athens, Greece
127 rdf:type schema:Organization
128 grid-institutes:grid.22401.35 schema:alternateName Tata Institute of Fundamental Research, Mumbai, India
129 schema:name Tata Institute of Fundamental Research, Mumbai, India
130 rdf:type schema:Organization
131 grid-institutes:grid.419528.3 schema:alternateName Max-Planck Institut für Informatik, Saarbrücken, Germany
132 schema:name Max-Planck Institut für Informatik, Saarbrücken, Germany
133 rdf:type schema:Organization
134 grid-institutes:grid.5371.0 schema:alternateName Chalmers University of Technology, Gothenburg, Sweden
135 schema:name Chalmers University of Technology, Gothenburg, Sweden
136 rdf:type schema:Organization
 




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


...