Pages that link to "Item:Q1315465"
From MaRDI portal
The following pages link to NP-completeness of minimum spanner problems (Q1315465):
Displaying 22 items.
- Approximating \(k\)-spanner problems for \(k>2\) (Q557826) (← links)
- Graph spanners in the streaming model: An experimental study (Q834593) (← links)
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model (Q838152) (← links)
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations (Q876695) (← links)
- Combinatorial network abstraction by trees and distances (Q954979) (← links)
- Edge-disjoint spanners of complete graphs and complete digraphs (Q1301660) (← links)
- Restrictions of minimum spanner problems (Q1370655) (← links)
- Spanners and message distribution in networks. (Q1427197) (← links)
- NP-hardness and fixed-parameter tractability of the minimum spanner problem (Q1784745) (← links)
- Graph spanners: a tutorial review (Q2026289) (← links)
- Sparsification lower bound for linear spanners in directed graphs (Q2055974) (← links)
- Minimum \(t\)-spanners on subcubic graphs (Q2154116) (← links)
- Parameterized complexity of directed spanner problems (Q2161008) (← links)
- Max-stretch reduction for tree spanners (Q2480904) (← links)
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs (Q2682929) (← links)
- COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD (Q3562852) (← links)
- A linear time algorithm to construct a tree 4-spanner on trapezoid graphs (Q3568416) (← links)
- ON SPANNERS OF GEOMETRIC GRAPHS (Q3620618) (← links)
- Light graphs with small routing cost (Q4537619) (← links)
- An optimal parallel algorithm to construct a tree 3-spanner on interval graphs (Q4653706) (← links)
- Tree spanners in planar graphs (Q5928870) (← links)
- Parameterized Complexity of Directed Spanner Problems. (Q6089656) (← links)
