On the crossing spanning tree problem

DOI10.1007/978-3-540-27821-4_5MaRDI QIDQ5313046zbMATH OpenOpenAlexFDO

Authors Vittorio Bilò, Vineet Goyal, R. Ravi, Mohit Singh

Publication date 25 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99805

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Spanning trees with low crossing number
• scientific article; zbMATH DE number 1303537
• scientific article; zbMATH DE number 437549
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Minimum cuts in near-linear time

Cited in

(10)

• The 2-hop spanning tree problem
• The parameterized complexity of stabbing rectangles
• Degree bounded matroids and submodular flows
• On the Red/Blue Spanning Tree Problem
• New approaches to multi-objective optimization
• Crossing-Free Spanning Trees in Visibility Graphs of Points between Monotone Polygonal Obstacles
• Fast diameter computation within split graphs
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• A Spectral Approach to Network Design
• On the SPANNING k-TREE problem

This page was built for publication: On the crossing spanning tree problem

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