Approximating Transitive Reductions for Directed Networks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Piotr Berman , Bhaskar DasGupta , Marek Karpinski

ABSTRACT

We consider minimum equivalent digraph problem, its maximum optimization variant and some non-trivial extensions of these two types of problems motivated by biological and social network applications. We provide \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{3}{2}$\end{document}-approximation algorithms for all the minimization problems and 2-approximation algorithms for all the maximization problems using appropriate primal-dual polytopes. We also show lower bounds on the integrality gap of the polytope to provide some intuition on the final limit of such approaches. Furthermore, we provide APX-hardness result for all those problems even if the length of all simple cycles is bounded by 5. More... »

PAGES

74-85

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03367-4_7

DOI

http://dx.doi.org/10.1007/978-3-642-03367-4_7

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Research partially done while visiting Dept. of Computer Science, University of Bonn and supported by DFG grant Bo 56/174-1, Pennsylvania State University, University Park, 16802, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Research partially done while visiting Dept. of Computer Science, University of Bonn and supported by DFG grant Bo 56/174-1, Pennsylvania State University, University Park, 16802, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Supported in part by DFG grants, Procope grant 31022, and Hausdorff Center research grant EXC59-1, University of Bonn, 53117, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Supported in part by DFG grants, Procope grant 31022, and Hausdorff Center research grant EXC59-1, University of Bonn, 53117, 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"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We consider minimum equivalent digraph problem, its maximum optimization variant and some non-trivial extensions of these two types of problems motivated by biological and social network applications. We provide \\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}$\\frac{3}{2}$\\end{document}-approximation algorithms for all the minimization problems and 2-approximation algorithms for all the maximization problems using appropriate primal-dual polytopes. We also show lower bounds on the integrality gap of the polytope to provide some intuition on the final limit of such approaches. Furthermore, we provide APX-hardness result for all those problems even if the length of all simple cycles is bounded by 5.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Gavrilova", 
        "givenName": "Marina", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "T\u00f3th", 
        "givenName": "Csaba D.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03367-4_7", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03366-7", 
        "978-3-642-03367-4"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "APX-hardness result", 
      "non-trivial extension", 
      "types of problems", 
      "digraph problems", 
      "Directed Networks", 
      "minimization problem", 
      "lower bounds", 
      "approximation algorithm", 
      "optimization variants", 
      "integrality gap", 
      "maximization problem", 
      "transitive reduction", 
      "polytope", 
      "simple cycle", 
      "problem", 
      "network applications", 
      "algorithm", 
      "bounds", 
      "such approaches", 
      "extension", 
      "final limit", 
      "intuition", 
      "network", 
      "applications", 
      "limit", 
      "approach", 
      "gap", 
      "results", 
      "social network applications", 
      "length", 
      "types", 
      "variants", 
      "reduction", 
      "cycle"
    ], 
    "name": "Approximating Transitive Reductions for Directed Networks", 
    "pagination": "74-85", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041450529"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03367-4_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03367-4_7", 
      "https://app.dimensions.ai/details/publication/pub.1041450529"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_53.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03367-4_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/978-3-642-03367-4_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/978-3-642-03367-4_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03367-4_7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03367-4_7'


 

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

129 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03367-4_7 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nfed440b336174f30a6931777395afbc1
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We consider minimum equivalent digraph problem, its maximum optimization variant and some non-trivial extensions of these two types of problems motivated by biological and social network applications. We provide \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{3}{2}$\end{document}-approximation algorithms for all the minimization problems and 2-approximation algorithms for all the maximization problems using appropriate primal-dual polytopes. We also show lower bounds on the integrality gap of the polytope to provide some intuition on the final limit of such approaches. Furthermore, we provide APX-hardness result for all those problems even if the length of all simple cycles is bounded by 5.
7 schema:editor N52aca9f5e1924410aba2c2372c02ae64
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfb6a4490d2db4e6583485e7234fdad05
12 schema:keywords APX-hardness result
13 Directed Networks
14 algorithm
15 applications
16 approach
17 approximation algorithm
18 bounds
19 cycle
20 digraph problems
21 extension
22 final limit
23 gap
24 integrality gap
25 intuition
26 length
27 limit
28 lower bounds
29 maximization problem
30 minimization problem
31 network
32 network applications
33 non-trivial extension
34 optimization variants
35 polytope
36 problem
37 reduction
38 results
39 simple cycle
40 social network applications
41 such approaches
42 transitive reduction
43 types
44 types of problems
45 variants
46 schema:name Approximating Transitive Reductions for Directed Networks
47 schema:pagination 74-85
48 schema:productId N58989973190d4c74919e9736d87220de
49 Nb3979a817f244fde978dcaf5f8339f2f
50 schema:publisher N4aff0162a736423ba5c050c7a1dc4f65
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041450529
52 https://doi.org/10.1007/978-3-642-03367-4_7
53 schema:sdDatePublished 2022-05-10T10:54
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Ndd631a40112243f3ad080b56820d5fd6
56 schema:url https://doi.org/10.1007/978-3-642-03367-4_7
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N0024fbff02934c9b8b7a6c7ffdca3a55 rdf:first N437eb2d2530b4d55abd2d2ee8a0aac10
61 rdf:rest N37683a197dc44c6fbc16bf4968f6577b
62 N017b73221cd24c22812197300fbdbb6e rdf:first sg:person.0763403270.10
63 rdf:rest Ne20985b7cc5a44beb62ee54604f43752
64 N37683a197dc44c6fbc16bf4968f6577b rdf:first Nbdef64cc561b4402b84abb41539c93ca
65 rdf:rest Na253e611cd1340f280b4d331d2133ee9
66 N437eb2d2530b4d55abd2d2ee8a0aac10 schema:familyName Gavrilova
67 schema:givenName Marina
68 rdf:type schema:Person
69 N4aff0162a736423ba5c050c7a1dc4f65 schema:name Springer Nature
70 rdf:type schema:Organisation
71 N52aca9f5e1924410aba2c2372c02ae64 rdf:first Ne06ff979af804cf1bfaba0f393c5553d
72 rdf:rest N0024fbff02934c9b8b7a6c7ffdca3a55
73 N58989973190d4c74919e9736d87220de schema:name doi
74 schema:value 10.1007/978-3-642-03367-4_7
75 rdf:type schema:PropertyValue
76 N9b7d9058af1f4465b005c5fa51ad9fcf schema:familyName Tóth
77 schema:givenName Csaba D.
78 rdf:type schema:Person
79 Na253e611cd1340f280b4d331d2133ee9 rdf:first N9b7d9058af1f4465b005c5fa51ad9fcf
80 rdf:rest rdf:nil
81 Nb3979a817f244fde978dcaf5f8339f2f schema:name dimensions_id
82 schema:value pub.1041450529
83 rdf:type schema:PropertyValue
84 Nbdef64cc561b4402b84abb41539c93ca schema:familyName Sack
85 schema:givenName Jörg-Rüdiger
86 rdf:type schema:Person
87 Ndd631a40112243f3ad080b56820d5fd6 schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Ne06ff979af804cf1bfaba0f393c5553d schema:familyName Dehne
90 schema:givenName Frank
91 rdf:type schema:Person
92 Ne20985b7cc5a44beb62ee54604f43752 rdf:first sg:person.011636042271.02
93 rdf:rest rdf:nil
94 Nfb6a4490d2db4e6583485e7234fdad05 schema:isbn 978-3-642-03366-7
95 978-3-642-03367-4
96 schema:name Algorithms and Data Structures
97 rdf:type schema:Book
98 Nfed440b336174f30a6931777395afbc1 rdf:first sg:person.01274506210.27
99 rdf:rest N017b73221cd24c22812197300fbdbb6e
100 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
101 schema:name Mathematical Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
104 schema:name Applied Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
107 schema:familyName Karpinski
108 schema:givenName Marek
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
110 rdf:type schema:Person
111 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
112 schema:familyName Berman
113 schema:givenName Piotr
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
115 rdf:type schema:Person
116 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
117 schema:familyName DasGupta
118 schema:givenName Bhaskar
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
120 rdf:type schema:Person
121 grid-institutes:grid.10388.32 schema:alternateName Supported in part by DFG grants, Procope grant 31022, and Hausdorff Center research grant EXC59-1, University of Bonn, 53117, Bonn, Germany
122 schema:name Supported in part by DFG grants, Procope grant 31022, and Hausdorff Center research grant EXC59-1, University of Bonn, 53117, Bonn, Germany
123 rdf:type schema:Organization
124 grid-institutes:grid.185648.6 schema:alternateName Supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
125 schema:name Supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973, University of Illinois at Chicago, 60607-7053, Chicago, IL, USA
126 rdf:type schema:Organization
127 grid-institutes:grid.29857.31 schema:alternateName Research partially done while visiting Dept. of Computer Science, University of Bonn and supported by DFG grant Bo 56/174-1, Pennsylvania State University, University Park, 16802, PA, USA
128 schema:name Research partially done while visiting Dept. of Computer Science, University of Bonn and supported by DFG grant Bo 56/174-1, Pennsylvania State University, University Park, 16802, PA, USA
129 rdf:type schema:Organization
 




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


...