On Linear Time Minor Tests with Depth-First Search

DOI10.1006/jagm.1993.1001zbMath0764.68107OpenAlexW2066904980WikidataQ56639266 ScholiaQ56639266MaRDI QIDQ4033754

Publication date: 16 May 1993

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1993.1001

zbMATH Keywords

dynamic programming cycle path grid graph graph minors depth- first search circus graph linear time minor tests

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (43)

Spotting Trees with Few Leaves ⋮ Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ Parameterized and approximation algorithms for finding two disjoint matchings ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ On the complexity of rainbow coloring problems ⋮ Narrow sieves for parameterized paths and packings ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Finding monotone paths in edge-ordered graphs ⋮ On interval routing schemes and treewidth ⋮ Algorithms for long paths in graphs ⋮ Integer programming methods for solving binary interdiction games ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Detours in directed graphs ⋮ Low Polynomial Exclusion of Planar Graph Patterns ⋮ On Interval Routing Schemes and treewidth ⋮ Safe Sets in Graphs: Graph Classes and Structural Parameters ⋮ Unnamed Item ⋮ Methods for determining cycles of a specific length in undirected graphs with edge weights ⋮ A new algorithm for minimum spanning tree using depth-first-search in an undirected graph ⋮ Going Far from Degeneracy ⋮ Subexponential parameterized algorithms ⋮ A new algorithm for finding trees with many leaves ⋮ An exact algorithm for the maximum leaf spanning tree problem ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Unnamed Item ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Algorithm for two disjoint long paths in 2-connected graphs ⋮ Nonempty intersection of longest paths in series-parallel graphs ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Two edge-disjoint paths with length constraints ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

This page was built for publication: On Linear Time Minor Tests with Depth-First Search