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/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/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"
      }, 
      {
        "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/11940128_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035181761", 
          "https://doi.org/10.1007/11940128_17"
        ], 
        "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-10-01T06:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_682.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 Ne769ca30710b4f40906094ae685c79f3
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 Nc0838c0001f74a8790b9bba7282ffddf
14 Ne04e50169ded400e947ef28f86b191f5
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 N17e640591c1a4549a56238cd9cc9c988
52 Na8bd3fb23b6946c4b972e58af34f7294
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-10-01T06:41
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N1ef85371f5c24b92a8316c6a6559dedd
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 N17e640591c1a4549a56238cd9cc9c988 schema:name dimensions_id
63 schema:value pub.1026774630
64 rdf:type schema:PropertyValue
65 N1ef85371f5c24b92a8316c6a6559dedd schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N58cc98c998df421c88a4a39bbe4501da rdf:first sg:person.011757371347.43
68 rdf:rest Nc68ae3a34d0546a68782c1347bec361b
69 N93b430e03adc404a96d8a6fa46ad5211 rdf:first sg:person.015551052213.83
70 rdf:rest N58cc98c998df421c88a4a39bbe4501da
71 Na8bd3fb23b6946c4b972e58af34f7294 schema:name doi
72 schema:value 10.1007/s00453-015-9994-9
73 rdf:type schema:PropertyValue
74 Nc0838c0001f74a8790b9bba7282ffddf schema:volumeNumber 74
75 rdf:type schema:PublicationVolume
76 Nc68ae3a34d0546a68782c1347bec361b rdf:first sg:person.07510643303.39
77 rdf:rest rdf:nil
78 Ne04e50169ded400e947ef28f86b191f5 schema:issueNumber 3
79 rdf:type schema:PublicationIssue
80 Ne769ca30710b4f40906094ae685c79f3 rdf:first sg:person.012535026361.26
81 rdf:rest N93b430e03adc404a96d8a6fa46ad5211
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)


...