Parameterized algorithms and data reduction for the short secluded s‐t‐path problem (Q6068532): Difference between revisions

Latest revision as of 18:08, 30 December 2024

scientific article; zbMATH DE number 7764301

Language	Label	Description	Also known as
English	Parameterized algorithms and data reduction for the short secluded <i>s</i>‐<i>t</i>‐path problem	scientific article; zbMATH DE number 7764301

Statements

instance of

scholarly article

0 references

title

Parameterized algorithms and data reduction for the short secluded s‐t‐path problem (English)

0 references

0 references

0 references

0 references

0 references

13 November 2023

0 references

full work available at URL

https://arxiv.org/abs/1806.09540

0 references

zbMATH Keywords

fixed-parameter tractability

0 references

kernelization lower bounds

0 references

NP-hard problem

0 references

problem kernelization

0 references

subexponential time

0 references

treewidth

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Not being (super)thin or solid is hard: A study of grid Hamiltonicity

0 references

Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

0 references

The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

0 references

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

0 references

On problems without polynomial kernels

0 references

A $c^k n$ 5-Approximation Algorithm for Treewidth

0 references

Kernelization Lower Bounds by Cross-Composition

0 references

The Minor Crossing Number

0 references

Q5009490

0 references

The parameterized approximability of TSP with deadlines

0 references

Secluded connectivity problems

0 references

Parameterized Algorithms

0 references

Q5111890

0 references

Linearity of grid minors in treewidth with applications through bidimensionality

0 references

Q3577833

0 references

Efficient Algorithms for Eulerian Extension and Rural Postman

0 references

Fundamentals of parameterized complexity

0 references

Polynomial kernels for weighted problems

0 references

Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions

0 references

On the parameterized complexity of multiple-interval graph problems

0 references

Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity

0 references

Parameterized approximation via fidelity preserving transformations

0 references

Parametrized complexity theory.

0 references

Parameterized complexity of secluded connectivity problems

0 references

An application of simultaneous diophantine approximation in combinatorial optimization

0 references

Q5111877

0 references

Parameterized complexity of the $k$-arc Chinese postman problem

0 references

The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

0 references

Parameterized complexity of $k$-Chinese postman problem

0 references

Parameterized Traveling Salesman Problem: Beating the Average

0 references

Rural postman parameterized by the number of components of required edges

0 references

A completeness theory for polynomial (Turing) kernelization

0 references

Which problems have strongly exponential complexity?

0 references

A subexponential parameterized algorithm for Subset TSP on planar graphs

0 references

Q4967164

0 references

Compression via Matroids

0 references

Lossy kernelization

0 references

Lower bounds on kernelization

0 references

Q5710169

0 references

From Few Components to an Eulerian Graph by Adding Arcs

0 references

A new view on rural postman based on Eulerian extension and matching

0 references

Über eine Eigenschaft der ebenen Komplexe

0 references

Identifiers

arXiv ID

1806.09540

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6068532

@@ Property / DOI @@
-.1002/net.21904
@@ Property / DOI: 10.1002/net.21904 / rank @@
-Normal rank
@@ Property / cites work @@
+Not being (super)thin or solid is hard: A study of grid Hamiltonicity
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
+Normal rank
@@ Property / cites work @@
+The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
+Normal rank
@@ Property / cites work @@
+Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+A $c^k n$ 5-Approximation Algorithm for Treewidth
@@ Property / cites work: A $c^k n$ 5-Approximation Algorithm for Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Kernelization Lower Bounds by Cross-Composition
@@ Property / cites work: Kernelization Lower Bounds by Cross-Composition / rank @@
+Normal rank
@@ Property / cites work @@
+The Minor Crossing Number
@@ Property / cites work: The Minor Crossing Number / rank @@
+Normal rank
@@ Property / cites work @@
+Q5009490
@@ Property / cites work: Q5009490 / rank @@
+Normal rank
@@ Property / cites work @@
+The parameterized approximability of TSP with deadlines
+Normal rank
@@ Property / cites work @@
+Secluded connectivity problems
@@ Property / cites work: Secluded connectivity problems / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111890
@@ Property / cites work: Q5111890 / rank @@
+Normal rank
@@ Property / cites work @@
+Linearity of grid minors in treewidth with applications through bidimensionality
+Normal rank
@@ Property / cites work @@
+Q3577833
@@ Property / cites work: Q3577833 / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Eulerian Extension and Rural Postman
+Normal rank
@@ Property / cites work @@
+Fundamentals of parameterized complexity
@@ Property / cites work: Fundamentals of parameterized complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial kernels for weighted problems
@@ Property / cites work: Polynomial kernels for weighted problems / rank @@
+Normal rank
@@ Property / cites work @@
+Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
+Normal rank
@@ Property / cites work @@
+On the parameterized complexity of multiple-interval graph problems
+Normal rank
@@ Property / cites work @@
+Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
+Normal rank
@@ Property / cites work @@
+Parameterized approximation via fidelity preserving transformations
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of secluded connectivity problems
+Normal rank
@@ Property / cites work @@
+An application of simultaneous diophantine approximation in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Q5111877
@@ Property / cites work: Q5111877 / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of the \(k\)-arc Chinese postman problem
+Normal rank
@@ Property / cites work @@
+The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of \(k\)-Chinese postman problem
+Normal rank
@@ Property / cites work @@
+Parameterized Traveling Salesman Problem: Beating the Average
+Normal rank
@@ Property / cites work @@
+Rural postman parameterized by the number of components of required edges
+Normal rank
@@ Property / cites work @@
+A completeness theory for polynomial (Turing) kernelization
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+A subexponential parameterized algorithm for Subset TSP on planar graphs
+Normal rank
@@ Property / cites work @@
+Q4967164
@@ Property / cites work: Q4967164 / rank @@
+Normal rank
@@ Property / cites work @@
+Compression via Matroids
@@ Property / cites work: Compression via Matroids / rank @@
+Normal rank
@@ Property / cites work @@
+Lossy kernelization
@@ Property / cites work: Lossy kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on kernelization
@@ Property / cites work: Lower bounds on kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+From Few Components to an Eulerian Graph by Adding Arcs
+Normal rank
@@ Property / cites work @@
+A new view on rural postman based on Eulerian extension and matching
+Normal rank
@@ Property / cites work @@
+Über eine Eigenschaft der ebenen Komplexe
@@ Property / cites work: Über eine Eigenschaft der ebenen Komplexe / rank @@
+Normal rank
@@ Property / DOI @@
+.1002/NET.21904
@@ Property / DOI: 10.1002/NET.21904 / rank @@
+Normal rank

Parameterized algorithms and data reduction for the short secluded <i>s</i>‐<i>t</i>‐path problem (Q6068532): Difference between revisions

Latest revision as of 18:08, 30 December 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)