Effective computation of immersion obstructions for unions of graph classes

DOI10.1016/j.jcss.2013.07.008zbMath1311.05168arXiv1207.5636OpenAlexW1949768901MaRDI QIDQ395009

Archontia C. Giannopoulou, Dimitris Zoros, Iosif Salem

Publication date: 28 January 2014

Published in: Journal of Computer and System Sciences, Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.5636

zbMATH Keywords

obstructionsimmersionstree-widthunique linkage theorem

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Sparse obstructions for minor-covering parameters ⋮ Forbidding Kuratowski Graphs as Immersions ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effective computation of immersion obstructions for unions of graph classes
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Forbidden graphs for tree-depth
• The multivariate algorithmic revolution and beyond. Essays dedicated to Michael R. Fellows on the occasion of his 60th birthday
• The structure of graphs not admitting a fixed immersion
• Graph minors. XX: Wagner's conjecture
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. XXI. graphs with unique linkages
• On problems without polynomial kernels
• Parameterized circuit complexity and the \(W\) hierarchy
• Quickly excluding a planar graph
• On search, decision, and the efficiency of polynomial-time algorithms
• Graph minors. XVI: Excluding a non-planar graph
• On computing graph minor obstruction sets
• Graph minors. XIII: The disjoint paths problem
• Characterizing graphs of small carving-width
• Parametrized complexity theory.
• A shorter proof of the graph minor algorithm
• Easy problems for tree-decomposable graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Fast FAST
• Nonconstructive tools for proving polynomial-time decidability
• Rankings of Graphs
• The size of an intertwine
• (Meta) Kernelization
• Finding topological subgraphs is fixed-parameter tractable
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: Effective computation of immersion obstructions for unions of graph classes