On the public citation graph

The complexity of induced minors and related problems

https://doi.org/10.1007/bf01190507

0 signed · 97 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/net.1975.5.1.45openalex-snapshot

On the Computational Complexity of Combinatorial Problems

inferredcites →https://doi.org/10.1007/bf02574704openalex-snapshot

Disjoint homotopic paths and trees in a planar graph

inferredcites →https://doi.org/10.1016/0012-365x(80)90158-2openalex-snapshot

Disjoint paths in graphs

inferredcites →https://doi.org/10.1016/0095-8956(85)90069-3openalex-snapshot

Graphs without K4 and well-quasi-ordering

inferredcites →https://doi.org/10.1016/0166-218x(88)90125-4openalex-snapshot

A note on odd/even cycles

inferredcites →https://doi.org/10.1016/0166-218x(92)90275-fopenalex-snapshot

Induced matchings

inferredcites →https://doi.org/10.1016/0304-3975(80)90009-2openalex-snapshot

The directed subgraph homeomorphism problem

inferredcites →https://doi.org/10.1016/0890-5401(90)90043-hopenalex-snapshot

The monadic second-order logic of graphs. I. Recognizable sets of finite graphs

inferredcites →https://doi.org/10.1016/j.disc.2006.03.019openalex-snapshot

Disjoint paths in graphs

inferredcites →https://doi.org/10.1016/s0195-6698(80)80039-4openalex-snapshot

2-Linked Graphs

inferredcites →https://doi.org/10.1090/conm/089/1006472openalex-snapshot

The Robertson-Seymour theorems: a survey of applications

inferredcites →https://doi.org/10.1109/tc.1981.6312176openalex-snapshot

Universality considerations in VLSI circuits

inferredcites →https://doi.org/10.1137/0211025openalex-snapshot

Planar Formulae and Their Uses

inferredcites →https://doi.org/10.1137/0404022openalex-snapshot

Noncrossing Subgraphs in Topological Layouts

inferredcites →https://doi.org/10.1145/167088.167161openalex-snapshot

A linear time algorithm for finding tree-decompositions of small treewidth

inferredcites →https://doi.org/10.1145/322203.322207openalex-snapshot

A Polynomial Solution to the Undirected Two Paths Problem

inferredcites →https://doi.org/10.6028/jres.069b.013openalex-snapshot

Maximum matching and a polyhedron with 0,1-vertices

What points at this work

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

inferred← citeshttps://doi.org/10.1002/jgt.22067openalex-snapshot

Partial Characterizations of 1‐Perfectly Orientable Graphs

inferred← citeshttps://doi.org/10.1006/jctb.1998.1846openalex-snapshot

Classes and Recognition of Curve Contact Graphs

inferred← citeshttps://doi.org/10.1007/11523468_30openalex-snapshot

Distance Constrained Labelings of Graphs of Bounded Treewidth

inferred← citeshttps://doi.org/10.1007/3-540-45477-2_23openalex-snapshot

Complexity of Coloring Graphs without Forbidden Induced Subgraphs

inferred← citeshttps://doi.org/10.1007/3-540-61534-2_19openalex-snapshot

Lattice embedding

inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_19openalex-snapshot

Applications of the Obstruction Principle and WQOs

inferred← citeshttps://doi.org/10.1007/978-3-030-00256-5_11openalex-snapshot

Computing Small Pivot-Minors

inferred← citeshttps://doi.org/10.1007/978-3-030-48966-3_4openalex-snapshot

Parameterized Complexity of $$(A,\ell )$$-Path Packing

inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_8openalex-snapshot

Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure

inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_9openalex-snapshot

Graph Isomorphism Restricted by Lists

inferred← citeshttps://doi.org/10.1007/978-3-031-52113-3_13openalex-snapshot

Data Reduction for Directed Feedback Vertex Set on Graphs Without Long Induced Cycles

inferred← citeshttps://doi.org/10.1007/978-3-031-63021-7_12openalex-snapshot

Detecting $$K_{2,3}$$ as an Induced Minor

inferred← citeshttps://doi.org/10.1007/978-3-031-82670-2_15openalex-snapshot

Sufficient Conditions for Polynomial-Time Detection of Induced Minors

inferred← citeshttps://doi.org/10.1007/978-3-032-11835-6_10openalex-snapshot

Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars

inferred← citeshttps://doi.org/10.1007/978-3-319-07557-0_34openalex-snapshot

Claw-Free t-Perfect Graphs Can Be Recognised in Polynomial Time

inferred← citeshttps://doi.org/10.1007/978-3-319-12340-0_12openalex-snapshot

Contact Representations of Planar Graphs: Extending a Partial Representation is Hard

inferred← citeshttps://doi.org/10.1007/978-3-319-13075-0_50openalex-snapshot

Planar Embeddings with Small and Uniform Faces

inferred← citeshttps://doi.org/10.1007/978-3-319-53925-6_8openalex-snapshot

A Width Parameter Useful for Chordal and Co-comparability Graphs

inferred← citeshttps://doi.org/10.1007/978-3-540-28639-4_3openalex-snapshot

Chordless Paths Through Three Vertices

inferred← citeshttps://doi.org/10.1007/978-3-540-68891-4_4openalex-snapshot

The Induced Disjoint Paths Problem

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-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-31155-0_14openalex-snapshot

Induced Disjoint Paths in AT-Free Graphs

inferred← citeshttps://doi.org/10.1007/978-3-642-33090-2_45openalex-snapshot

Induced Disjoint Paths in Claw-Free Graphs

inferred← citeshttps://doi.org/10.1007/978-3-642-33293-7_19openalex-snapshot

MSOL Restricted Contractibility to Planar Graphs

inferred← citeshttps://doi.org/10.1007/978-3-642-35261-4_33openalex-snapshot

Induced Immersions

inferred← citeshttps://doi.org/10.1007/978-3-642-35261-4_52openalex-snapshot

Detecting Induced Minors in AT-Free Graphs

inferred← citeshttps://doi.org/10.1007/978-3-642-38236-9_11openalex-snapshot

Non-crossing Connectors in the Plane

inferred← citeshttps://doi.org/10.1007/978-3-642-45278-9_17openalex-snapshot

Graph Editing to a Fixed Target

inferred← citeshttps://doi.org/10.1007/978-3-662-53174-7_21openalex-snapshot

Induced Minor Free Graphs: Isomorphism and Clique-width

inferred← citeshttps://doi.org/10.1007/978-981-95-7127-7_32openalex-snapshot

The Gate-Cover Problem

inferred← citeshttps://doi.org/10.1007/s00236-025-00490-2openalex-snapshot

Data reduction for directed feedback vertex set on graphs without long induced cycles

inferred← citeshttps://doi.org/10.1007/s00453-005-1176-8openalex-snapshot

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

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.1007/s00453-016-0234-8openalex-snapshot

Induced Minor Free Graphs: Isomorphism and Clique-Width

inferred← citeshttps://doi.org/10.1007/s00453-020-00737-zopenalex-snapshot

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

inferred← citeshttps://doi.org/10.1007/s00453-021-00875-yopenalex-snapshot

Parameterized Complexity of $$(A,\ell )$$-Path Packing

inferred← citeshttps://doi.org/10.1007/s00493-010-2499-xopenalex-snapshot

Algorithms for finding an induced cycle in planar graphs

inferred← citeshttps://doi.org/10.1016/0166-218x(94)90150-3openalex-snapshot

Algorithmic complexity of list colorings

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.2014.07.008openalex-snapshot

Graph editing to a fixed target

inferred← citeshttps://doi.org/10.1016/j.dam.2017.09.017openalex-snapshot

1 -perfectly orientable K4 -minor-free and outerplanar graphs

inferred← citeshttps://doi.org/10.1016/j.dam.2024.09.011openalex-snapshot

Recognizing unit multiple interval graphs is hard

inferred← citeshttps://doi.org/10.1016/j.endm.2016.09.035openalex-snapshot

1-perfectly orientable K 4 -minor-free and outerplanar graphs

inferred← citeshttps://doi.org/10.1016/j.endm.2017.06.053openalex-snapshot

Contracting Bipartite Graphs to Paths and Cycles

inferred← citeshttps://doi.org/10.1016/j.ic.2024.105227openalex-snapshot

Blazing a trail via matrix multiplications: A faster algorithm for non-shortest induced paths

inferred← citeshttps://doi.org/10.1016/j.jcss.2011.10.004openalex-snapshot

A linear time algorithm for the induced disjoint paths problem in planar graphs

inferred← citeshttps://doi.org/10.1016/j.jcss.2025.103738openalex-snapshot

Induced minor models. I. Structural properties and algorithmic consequences

inferred← citeshttps://doi.org/10.1016/j.jctb.2020.06.002openalex-snapshot

The (theta, wheel)-free graphs Part IV: Induced paths and cycles

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.2005.10.021openalex-snapshot

Chordless paths through three vertices

inferred← citeshttps://doi.org/10.1016/j.tcs.2012.09.007openalex-snapshot

Hypertree-depth and minors in hypergraphs

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.2014.10.044openalex-snapshot

On a class of covering problems with variable capacities in wireless networks

inferred← citeshttps://doi.org/10.1016/j.tcs.2017.02.030openalex-snapshot

MSOL restricted contractibility to planar graphs

inferred← citeshttps://doi.org/10.1109/tnet.2020.2975646openalex-snapshot

On the Hardness and Inapproximability of Virtual Network Embeddings

inferred← citeshttps://doi.org/10.1137/1.9781611975994.56openalex-snapshot

Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

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/100803870openalex-snapshot

Gallai's Theorem for List Coloring of Digraphs

inferred← citeshttps://doi.org/10.1137/140963200openalex-snapshot

Induced Disjoint Paths in Claw-Free Graphs

inferred← citeshttps://doi.org/10.1137/151006111openalex-snapshot

Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time

inferred← citeshttps://doi.org/10.1137/20m1352119openalex-snapshot

Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

inferred← citeshttps://doi.org/10.1142/9781860947995_0018openalex-snapshot

FITTING PROTEIN CHAINS TO CUBIC LATTICE IS NP-COMPLETE

inferred← citeshttps://doi.org/10.1142/s0219720008003308openalex-snapshot

FITTING PROTEIN CHAINS TO CUBIC LATTICE IS NP-COMPLETE

inferred← citeshttps://doi.org/10.1145/3519028openalex-snapshot

k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms

inferred← citeshttps://doi.org/10.1145/3583688openalex-snapshot

Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

inferred← citeshttps://doi.org/10.23638/dmtcs-21-3-18openalex-snapshot

Planar 3-SAT with a Clause/Variable Cycle

inferred← citeshttps://doi.org/10.31390/gradschool_dissertations.2224openalex-snapshot

Well-Quasi-Ordering by the Induced-Minor Relation

inferred← citeshttps://doi.org/10.3390/a11060084openalex-snapshot

Efficient Approximation for Restricted Biclique Cover Problems

inferred← citeshttps://doi.org/10.3390/appliedmath6100163openalex-snapshot

Maximum Induced Matching: Recursive Computation and an Availability-Uniform Branch-Length Analysis

inferred← citeshttps://doi.org/10.37236/1579openalex-snapshot

On Planar Mixed Hypergraphs

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2012.182openalex-snapshot

Contraction checking in graphs on surfaces

inferred← citeshttps://doi.org/10.46298/dmtcs.605openalex-snapshot

A note on contracting claw-free graphs

inferred← citeshttps://doi.org/10.48550/arxiv.1201.0917openalex-snapshot

Non-crossing Connectors in the Plane

inferred← citeshttps://doi.org/10.48550/arxiv.1204.6070openalex-snapshot

MSOL Restricted Contractibility to Planar Graphs

inferred← citeshttps://doi.org/10.48550/arxiv.1409.2733openalex-snapshot

Scattered packings of cycles

inferred← citeshttps://doi.org/10.5555/1496770.1496894openalex-snapshot

Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

inferred← citeshttps://doi.org/10.70675/e6355c4bz172az40e5z90a6ze5635bc0e918openalex-snapshot

Structural and algorithmic aspects of (multiple) interval 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.