On the public citation graph

Approximation Algorithms for Graph Homomorphism Problems

0 signed · 55 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-zopenalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.1002/1098-2418(200010/12)17:3/4<260::aid-rsa5>3.0.co;2-wopenalex-snapshot
The complexity of counting graph homomorphisms
inferredcites →https://doi.org/10.1002/rsa.20036openalex-snapshot
Corrigendum: The complexity of counting graph homomorphisms
inferredcites →https://doi.org/10.1006/jagm.2000.1142openalex-snapshot
On Markov Chains for Randomly H-Coloring a Graph
inferredcites →https://doi.org/10.1006/jcss.1998.1605openalex-snapshot
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
inferredcites →https://doi.org/10.1006/jcss.1999.1687openalex-snapshot
An Improved Approximation Algorithm for MULTIWAY CUT
inferredcites →https://doi.org/10.1006/jctb.1997.1812openalex-snapshot
List Homomorphisms to Reflexive Graphs
inferredcites →https://doi.org/10.1007/3-540-10003-2_79openalex-snapshot
On observing nondeterminism and concurrency
inferredcites →https://doi.org/10.1007/3-540-36379-3_12openalex-snapshot
The Complexity of Restrictive H-Coloring
inferredcites →https://doi.org/10.1007/3-540-48224-5_18openalex-snapshot
The RPR 2 Rounding Technique for Semidefinite Programs
inferredcites →https://doi.org/10.1007/3-540-55210-3_198openalex-snapshot
On the approximability of the maximum common subgraph problem
inferredcites →https://doi.org/10.1016/0095-8956(90)90132-jopenalex-snapshot
On the complexity of H-coloring
inferredcites →https://doi.org/10.1016/j.dam.2005.06.012openalex-snapshot
Level of repair analysis and minimum cost homomorphisms of graphs
inferredcites →https://doi.org/10.1016/j.jalgor.2004.11.003openalex-snapshot
The RPR2 rounding technique for semidefinite programs
inferredcites →https://doi.org/10.1016/s0020-0190(00)00065-xopenalex-snapshot
A lower bound of on the integrality ratio of the Călinescu–Karloff–Rabani relaxation for multiway cut
inferredcites →https://doi.org/10.1023/b:aire.0000044479.89075.02openalex-snapshot
About the Authors
inferredcites →https://doi.org/10.1093/acprof:oso/9780198528173.001.0001openalex-snapshot
Graphs and Homomorphisms
inferredcites →https://doi.org/10.1109/focs.2004.39openalex-snapshot
Maximizing Quadratic Programs: Extending Grothendieck's Inequality
inferredcites →https://doi.org/10.1109/sfcs.2003.1238204openalex-snapshot
More on average case vs approximation complexity
inferredcites →https://doi.org/10.1137/0209047openalex-snapshot
Random Graph Isomorphism
inferredcites →https://doi.org/10.1137/s0097539792225297openalex-snapshot
The Complexity of Multiterminal Cuts
inferredcites →https://doi.org/10.1145/1109557.1109577openalex-snapshot
Combination can be hard
inferredcites →https://doi.org/10.1145/227683.227684openalex-snapshot
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
inferredcites →https://doi.org/10.1145/509907.509985openalex-snapshot
Relations between average case complexity and approximation complexity
inferredcites →https://doi.org/10.1145/585265.585268openalex-snapshot
Approximation algorithms for classification problems with pairwise relationships
inferredcites →https://doi.org/10.1287/moor.1030.0086openalex-snapshot
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
inferredcites →https://doi.org/10.4064/cm-13-2-251-254openalex-snapshot
On an extremal problem in graph theory
inferredcites →https://doi.org/10.5555/1109557.1109577openalex-snapshot
Combination can be hard: approximability of the unique coverage problem
inferredcites →https://doi.org/10.5555/251040.251043openalex-snapshot
Algorithmic theory of random graphs

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-57602-8_15openalex-snapshot
Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph
inferred← citeshttps://doi.org/10.1007/978-3-031-20350-3_7openalex-snapshot
New Algorithms for a Simple Measure of Network Partitioning
inferred← citeshttps://doi.org/10.1007/978-3-319-21398-9_13openalex-snapshot
Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-44543-4_22openalex-snapshot
Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
inferred← citeshttps://doi.org/10.1007/978-3-319-48749-6_4openalex-snapshot
Approximation and Hardness Results for the Max k-Uncut Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_11openalex-snapshot
Approximability Distance in the Space of H-Colourability Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_15openalex-snapshot
Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-32589-2_12openalex-snapshot
Approximate Graph Isomorphism
inferred← citeshttps://doi.org/10.1007/s00453-017-0302-8openalex-snapshot
Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
inferred← citeshttps://doi.org/10.1007/s40305-019-00260-1openalex-snapshot
Approximation Algorithms for Vertex Happiness
inferred← citeshttps://doi.org/10.1016/j.tcs.2017.09.003openalex-snapshot
Approximation and hardness results for the Max k-Uncut problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.06.002openalex-snapshot
Parameterized complexity of happy coloring problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.10.018openalex-snapshot
Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph
inferred← citeshttps://doi.org/10.1080/02331934.2011.592527openalex-snapshot
An approximation algorithm for maxk-uncut with capacity constraints
inferred← citeshttps://doi.org/10.1109/cso.2009.443openalex-snapshot
An Approximation Algorithm for Max k-Uncut with Capacity Constraints
inferred← citeshttps://doi.org/10.1137/19m1290899openalex-snapshot
Minimum Violation Vertex Maps and Their Applications to Cut Problems
inferred← citeshttps://doi.org/10.1145/2229012.2229016openalex-snapshot
Combinatorial auctions with restricted complements
inferred← citeshttps://doi.org/10.1145/3626515openalex-snapshot
Pliability and Approximating Max-CSPs
inferred← citeshttps://doi.org/10.1145/3798129.3800853openalex-snapshot
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
inferred← citeshttps://doi.org/10.14778/3407790.3407834openalex-snapshot
Fast and effective distribution-key recommendation for amazon redshift
inferred← citeshttps://doi.org/10.15807/jorsj.55.92openalex-snapshot
OPTIMAL ALLOCATION PROBLEM WITH QUADRATIC UTILITY FUNCTIONS AND ITS RELATIONSHIP WITH GRAPH CUT PROBLEM
inferred← citeshttps://doi.org/10.1609/aaai.v28i1.8789openalex-snapshot
Approximate Equilibrium and Incentivizing Social Coordination
inferred← citeshttps://doi.org/10.4086/toc.2011.v007a005openalex-snapshot
inferred← citeshttps://doi.org/10.48550/arxiv.1404.4718openalex-snapshot
Approximate Equilibrium and Incentivizing Social Coordination
inferred← citeshttps://doi.org/10.48550/arxiv.1406.3514openalex-snapshot
Limits of CSP Problems and Efficient Parameter Testing
inferred← citeshttps://doi.org/10.48550/arxiv.1705.08282openalex-snapshot
Algorithms and hardness results for happy coloring problems
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.