On Linear Time Minor Tests with Depth-First Search

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)

Recommendations

scientific article; zbMATH DE number 140499
Fast minor testing in planar graphs
Fast minor testing in planar graphs
scientific article; zbMATH DE number 1264417
Minimax trees in linear time with applications
Minimax Trees in Linear Time with Applications
An optimal tester for \(k\)-linear
An optimal tester for k-Linear
scientific article; zbMATH DE number 1875415
An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees

Cited in

(47)

The \(k\)-distinct language: parameterized automata constructions
A new algorithm for finding trees with many leaves
Two edge-disjoint paths with length constraints
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
An exact algorithm for the maximum leaf spanning tree problem
A new algorithm for minimum spanning tree using depth-first-search in an undirected graph
Algorithm for two disjoint long paths in 2-connected graphs
Approximation and kernelization for chordal vertex deletion
Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
Safe sets in graphs: graph classes and structural parameters
Finding monotone paths in edge-ordered graphs
Faster deterministic parameterized algorithm for k-path
Safe sets in graphs: graph classes and structural parameters
A partial k-arboretum of graphs with bounded treewidth
Approximating long cycle above Dirac's guarantee
Spotting trees with few leaves
Parameterized and approximation algorithms for finding two disjoint matchings
scientific article; zbMATH DE number 7525484 (Why is no real title available?)
A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
Nonempty intersection of longest paths in series-parallel graphs
Complexity framework for forbidden subgraphs. I: The framework
Approximating the maximum clique minor and some subgraph homeomorphism problems
Detours in directed graphs
On the space and circuit complexity of parameterized problems: classes and completeness
On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves
On interval routing schemes and treewidth
Methods for determining cycles of a specific length in undirected graphs with edge weights
A Simple 2-Approximation for Maximum-Leaf Spanning Tree
Mineurs d'arbres avec racines
Subexponential parameterized algorithms
Narrow sieves for parameterized paths and packings
Low polynomial exclusion of planar graph patterns
Integer programming methods for solving binary interdiction games
Finding two edge-disjoint paths with length constraints
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Going far from degeneracy
Finding detours is fixed-parameter tractable
An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
Algorithms for long paths in graphs
Algorithm engineering for color-coding with applications to signaling pathway detection
A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
scientific article; zbMATH DE number 140499 (Why is no real title available?)
Parameterized algorithms for list \(K\)-cycle
Minors in graphs of large _r-girth
On Interval Routing Schemes and treewidth
On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4033754)