Sökning: onr:"swepub:oai:DiVA.org:liu-56791" >
Retractions To Pseu...
Retractions To Pseudoforests
-
- Feder, Tomas (författare)
- Stanford University
-
- Hell, Pavol (författare)
- Simon Fraser University
-
- Jonsson, Peter (författare)
- Linköpings universitet,TCSLAB - Laboratoriet för teoretisk datalogi,Tekniska högskolan
-
visa fler...
-
- Krokhin, Andrei (författare)
- University of Durham
-
- Nordh, Gustav (författare)
- Linköpings universitet,TCSLAB - Laboratoriet för teoretisk datalogi,Tekniska högskolan
-
visa färre...
-
(creator_code:org_t)
- Society for Industrial and Applied Mathematics, 2010
- 2010
- Engelska.
-
Ingår i: SIAM JOURNAL ON DISCRETE MATHEMATICS. - : Society for Industrial and Applied Mathematics. - 0895-4801 .- 1095-7146. ; 24:1, s. 101-112
- Relaterad länk:
-
http://theory.stanfo...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- For a fixed graph H, let RET(H) denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of RET(H) when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of RET(H) for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.
Nyckelord
- retraction
- computational complexity
- universal algebra
- constraint satisfaction
- TECHNOLOGY
- TEKNIKVETENSKAP
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas