On the public citation graph

The computational complexity of graph contractions II: Two tough polynomially solvable cases

0 signed · 24 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/jgt.3190110111openalex-snapshot
Contractibility and NP‐completeness
inferredcites →https://doi.org/10.1002/net.20214openalex-snapshot
The computational complexity of graph contractions I: Polynomially solvable and NP‐complete cases
inferredcites →https://doi.org/10.1006/jctb.1995.1006openalex-snapshot
Graph Minors .XIII. The Disjoint Paths Problem
inferredcites →https://doi.org/10.1007/978-1-349-03521-2openalex-snapshot
Graph Theory with Applications
inferredcites →https://doi.org/10.1145/322203.322207openalex-snapshot
A Polynomial Solution to the Undirected Two Paths Problem

What points at this work

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

inferred← citeshttps://doi.org/10.1002/net.20214openalex-snapshot
The computational complexity of graph contractions I: Polynomially solvable and NP‐complete cases
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.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.1587/transfun.e100.a.1764openalex-snapshot
A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth
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.