Back to Search
Start Over
On NC algorithms for problems on bounded rank-width graphs
- Source :
- Information Processing Letters. 139:64-67
- Publication Year :
- 2018
- Publisher :
- Elsevier BV, 2018.
-
Abstract
- In this paper, we show that for a fixed k, there is an NC algorithm that separates the graphs of rank-width at most k from those with rank-width at least<br />by Bireswar Das, Anirban Dasgupta, Murali Krishna Enduri, and Vinod I. Reddy<br />2018-08-10 12:16:50<br />https://doi.org/10.1016/j.ipl.2018.07.007
- Subjects :
- Parallel algorithms
Clique-width
Parallel algorithm
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Computer Science Applications
Theoretical Computer Science
010201 computation theory & mathematics
Bounded function
Signal Processing
0202 electrical engineering, electronic engineering, information engineering
Rank (graph theory)
020201 artificial intelligence & image processing
Rank-width
NP-complete
Algorithm
Information Systems
Mathematics
Subjects
Details
- ISSN :
- 00200190
- Volume :
- 139
- Database :
- OpenAIRE
- Journal :
- Information Processing Letters
- Accession number :
- edsair.doi.dedup.....ffdd3c73f60277bd19055a87dd4d56f6
- Full Text :
- https://doi.org/10.1016/j.ipl.2018.07.007