On the public citation graph
The computational complexity of graph contractions I: Polynomially solvable and NP‐complete cases
0 signed · 38 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/jgt.3190110111openalex-snapshot
Contractibility and NP‐completeness
inferredcites →https://doi.org/10.1002/net.20249openalex-snapshot
The computational complexity of graph contractions II: Two tough polynomially solvable cases
inferredcites →https://doi.org/10.1006/jctb.1995.1006openalex-snapshot
Graph Minors .XIII. The Disjoint Paths Problem
inferredcites →https://doi.org/10.1007/11809678_22openalex-snapshot
Restricted Mesh Simplification Using Edge Contractions
inferredcites →https://doi.org/10.1007/3-540-45294-x_3openalex-snapshot
On Clustering Using Random Walks
inferredcites →https://doi.org/10.1007/978-1-349-03521-2openalex-snapshot
Graph Theory with Applications
inferredcites →https://doi.org/10.1016/0012-365x(81)90022-4openalex-snapshot
Contraction theorems in Hamiltonian graph theory
inferredcites →https://doi.org/10.1016/0166-218x(83)90101-4openalex-snapshot
On the NP-hardness of edge-deletion and -contraction problems
inferredcites →https://doi.org/10.1016/j.comgeo.2003.07.001openalex-snapshot
Hierarchy of surface models and irreducible triangulations
inferredcites →https://doi.org/10.1109/tcad.2004.823353openalex-snapshot
Edge Separability-Based Circuit Clustering With Application to Multilevel Circuit Partitioning
inferredcites →https://doi.org/10.1137/s1064827595287997openalex-snapshot
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/jcc.21738openalex-snapshot
Fast construction of assembly trees for molecular graphs
inferred← citeshttps://doi.org/10.1002/net.20249openalex-snapshot
The computational complexity of graph contractions II: Two tough polynomially solvable cases
inferred← citeshttps://doi.org/10.1007/978-3-031-15914-5_26openalex-snapshot
The Complexity of Contracting Bipartite Graphs into Small Cycles
inferred← citeshttps://doi.org/10.1007/978-3-642-11266-9_42openalex-snapshot
On Contracting Graphs to Fixed Pattern Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-15775-2_11openalex-snapshot
Contractions of Planar Graphs in Polynomial Time
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_51openalex-snapshot
Edge Contractions in Subclasses of Chordal Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-22993-0_32openalex-snapshot
Contracting a Chordal Graph to a Split Graph or a Tree
inferred← citeshttps://doi.org/10.1007/978-3-642-25591-5_13openalex-snapshot
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
inferred← citeshttps://doi.org/10.1007/978-3-642-28050-4_6openalex-snapshot
Increasing the Minimum Degree of a Graph by Contractions
inferred← citeshttps://doi.org/10.1007/s00453-013-9748-5openalex-snapshot
Detecting Fixed Patterns in Chordal Graphs in Polynomial Time
inferred← citeshttps://doi.org/10.1016/j.dam.2010.05.005openalex-snapshot
On graph contractions and induced minors
inferred← citeshttps://doi.org/10.1016/j.dam.2011.10.004openalex-snapshot
Containment relations in split graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2011.12.012openalex-snapshot
Edge contractions in subclasses of chordal graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2013.02.025openalex-snapshot
Contracting chordal graphs and bipartite graphs to paths and trees
inferred← citeshttps://doi.org/10.1016/j.disc.2022.112877openalex-snapshot
Modulo orientations and matchings in graphs
inferred← citeshttps://doi.org/10.1016/j.endm.2011.05.016openalex-snapshot
Contracting chordal graphs and bipartite graphs to paths and trees
inferred← citeshttps://doi.org/10.1016/j.jda.2011.03.010openalex-snapshot
Contracting planar graphs to contractions of triangulations
inferred← citeshttps://doi.org/10.1016/j.jda.2012.11.002openalex-snapshot
Detecting induced star-like minors in polynomial time
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.02.029openalex-snapshot
Detecting induced minors in AT-free graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.02.030openalex-snapshot
Increasing the minimum degree of a graph by contractions
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch141openalex-snapshot
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
inferred← citeshttps://doi.org/10.1137/130907392openalex-snapshot
Obtaining a Bipartite Graph by Contracting Few Edges
inferred← citeshttps://doi.org/10.1587/transfun.e100.a.1764openalex-snapshot
A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth
inferred← citeshttps://doi.org/10.2139/ssrn.5083035openalex-snapshot
The GOOGLE and XPRIZE award for how to use quantum computers practically: The problem of the "P" versus "NP" outputs of any quantum computer and the pathway for its resolving
inferred← citeshttps://doi.org/10.33915/etd.7757openalex-snapshot
Weighted Modulo Orientations of Graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.2092openalex-snapshot
Complexity of conditional colouring with given template
inferred← citeshttps://doi.org/10.46298/dmtcs.605openalex-snapshot
A note on contracting claw-free graphs
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.