Marek Karpinski

Ontology type: schema:Person     

Person Info





Publications in SciGraph latest 50 shown

  • 2017-02-17 Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications in ALGORITHMICA
  • 2017-01-05 Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields in ALGORITHMICA
  • 2016 Tropical Dominating Sets in Vertex-Coloured Graphs in WALCOM: ALGORITHMS AND COMPUTATION
  • 2015-08-04 Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies in FUNDAMENTALS OF COMPUTATION THEORY
  • 2015-06-20 A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • 2014 Approximate Counting of Matchings in (3,3)-Hypergraphs in ALGORITHM THEORY – SWAT 2014
  • 2013-03-26 On the Computational Complexity of Measuring Global Stability of Banking Networks in ALGORITHMICA
  • 2013 New Inapproximability Bounds for TSP in ALGORITHMS AND COMPUTATION
  • 2011-11-16 Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems in ALGORITHMICA
  • 2011 Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • 2010 Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament in ALGORITHMS AND COMPUTATION
  • 2010 Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs in LATIN 2010: THEORETICAL INFORMATICS
  • 2010 Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems in COMPUTING AND COMBINATORICS
  • 2010 A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2 in ALGORITHMS AND COMPUTATION
  • 2009 Space Efficient Multi-dimensional Range Reporting in COMPUTING AND COMBINATORICS
  • 2009 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 in ALGORITHMS AND DATA STRUCTURES
  • 2009 Approximating Transitive Reductions for Directed Networks in ALGORITHMS AND DATA STRUCTURES
  • 2009 The Complexity of Perfect Matching Problems on Dense Hypergraphs in ALGORITHMS AND COMPUTATION
  • 2007-12-14 A Fast Algorithm for Adaptive Prefix Coding in ALGORITHMICA
  • 2007 Optimal Trade-Off for Merkle Tree Traversal in E-BUSINESS AND TELECOMMUNICATION NETWORKS
  • 2006 Stopping Times, Metrics and Approximate Counting in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2005-03-02 Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem in ALGORITHMICA
  • 2005 Embedding Point Sets into Plane Graphs of Small Dilation in ALGORITHMS AND COMPUTATION
  • 2005 On the Complexity of Global Constraint Satisfaction in ALGORITHMS AND COMPUTATION
  • 2005 Predecessor Queries in Constant Time? in ALGORITHMS – ESA 2005
  • 2005 Path Coupling Using Stopping Times in FUNDAMENTALS OF COMPUTATION THEORY
  • 2003 Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem in ALGORITHMS AND DATA STRUCTURES
  • 2002-10-04 Approximability of the Minimum Bisection Problem: An Algorithmic Challenge in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002
  • 2002-08-29 1.375-Approximation Algorithm for Sorting by Reversals in ALGORITHMS — ESA 2002
  • 2002-06-25 Approximating Huffman Codes in Parallel in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2002-06-25 Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2002-06-21 Approximability of Dense Instances of Nearest Codeword Problem in ALGORITHM THEORY — SWAT 2002
  • 2001-08-02 On Computational Power of Quantum Branching Programs in FUNDAMENTALS OF COMPUTATION THEORY
  • 2001-08-02 Approximating Bounded Degree Instances of NP-Hard Problems in FUNDAMENTALS OF COMPUTATION THEORY
  • 2001-07-04 Approximation Hardness of TSP with Bounded Metrics in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1999-07 On a New High Dimensional Weisfeiler-Lehman Algorithm in JOURNAL OF ALGEBRAIC COMBINATORICS
  • 1999 Quantum Finite Multitape Automata in SOFSEM’99: THEORY AND PRACTICE OF INFORMATICS
  • 1999 On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials in APPLIED ALGEBRA, ALGEBRAIC ALGORITHMS AND ERROR-CORRECTING CODES
  • 1999 On Some Tighter Inapproximability Results (Extended Abstract) in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1998-12 An exponential lower bound on the size of algebraic decision trees for Max in COMPUTATIONAL COMPLEXITY
  • 1997-03 Lower bound on testing membership to a polyhedron by algebraic decision and computation trees in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1997-03 New Approximation Algorithms for the Steiner Tree Problems in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 1997 Approximating the volume of general Pfaffian bodies in STRUCTURES IN LOGIC AND COMPUTER SCIENCE
  • 1997 On the complexity of pattern matching for highly compressed two-dimensional texts in COMBINATORIAL PATTERN MATCHING
  • 1997 On-line load balancing for related machines in ALGORITHMS AND DATA STRUCTURES
  • 1997 Effects of Kolmogorov complexity present in inductive inference as well in ALGORITHMIC LEARNING THEORY
  • 1997 Weak and strong recognition by 2-way randomized automata in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE
  • 1997 Polynomial time approximation schemes for some dense instances of NP-hard optimization problems in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE
  • 1996-12 Randomization and the computational power of analytic and algebraic decision trees in COMPUTATIONAL COMPLEXITY
  • 1996-12 A lower bound for randomized algebraic decision trees in COMPUTATIONAL COMPLEXITY
  • 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": "", 
        "affiliation": [
            "affiliation": {
              "id": "", 
              "type": "Organization"
            "isCurrent": true, 
            "type": "OrganizationRole"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
            "id": "", 
            "type": "Organization"
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
        "sdDataset": "persons", 
        "sdDatePublished": "2022-09-02T16:34", 
        "sdLicense": "", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/person/person_788.jsonl", 
        "type": "Person"

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


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

    curl -H 'Accept: application/ld+json' ''

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

    curl -H 'Accept: application/n-triples' ''

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' ''

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

    curl -H 'Accept: application/rdf+xml' ''


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

    32 TRIPLES      10 PREDICATES      19 URIs      7 LITERALS      2 BLANK NODES

    Subject Predicate Object
    1 sg:person.011636042271.02 schema:affiliation N8ddef1110a614be3bc54d4ab8c9e1cb0
    2 grid-institutes:grid.1013.3
    3 grid-institutes:grid.13992.30
    4 grid-institutes:grid.185107.a
    5 grid-institutes:grid.21925.3d
    6 grid-institutes:grid.410511.0
    7 grid-institutes:grid.5477.1
    8 grid-institutes:grid.6190.e
    9 grid-institutes:grid.77268.3c
    10 schema:familyName Karpinski
    11 schema:givenName Marek
    12 schema:sameAs
    13 schema:sdDatePublished 2022-09-02T16:34
    14 schema:sdLicense
    15 schema:sdPublisher N1d45a7a74c274b9c876849bd70a32437
    16 sgo:license sg:explorer/license/
    17 sgo:sdDataset persons
    18 rdf:type schema:Person
    19 N1d45a7a74c274b9c876849bd70a32437 schema:name Springer Nature - SN SciGraph project
    20 rdf:type schema:Organization
    21 N8ddef1110a614be3bc54d4ab8c9e1cb0 schema:affiliation grid-institutes:grid.10388.32
    22 sgo:isCurrent true
    23 rdf:type schema:OrganizationRole
    24 grid-institutes:grid.1013.3 schema:Organization
    25 grid-institutes:grid.10388.32 schema:Organization
    26 grid-institutes:grid.13992.30 schema:Organization
    27 grid-institutes:grid.185107.a schema:Organization
    28 grid-institutes:grid.21925.3d schema:Organization
    29 grid-institutes:grid.410511.0 schema:Organization
    30 grid-institutes:grid.5477.1 schema:Organization
    31 grid-institutes:grid.6190.e schema:Organization
    32 grid-institutes:grid.77268.3c schema:Organization

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