P.A. Golovach
Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
Golovach, P.A.; Paulusma, D.; van Leeuwen, E.J.
Abstract
The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (si,ti) contains paths P1,…,Pk such that Pi connects si and ti for i=1,…,k, and Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their ends) for 1≤i
Citation
Golovach, P., Paulusma, D., & van Leeuwen, E. (2014, December). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. Presented at 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 40th International Workshop, WG 2014 |
Publication Date | Jan 1, 2014 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Jan 17, 2015 |
Print ISSN | 0302-9743 |
Pages | 225-237 |
Series Title | Lecture notes in computer science |
Series Number | 8747 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, 25-27 June 2014 ; revised selected papers. |
ISBN | 978-3-319-12339-4 |
DOI | https://doi.org/10.1007/978-3-319-12340-0_19 |
Public URL | https://durham-repository.worktribe.com/output/1153916 |
Files
Accepted Conference Proceeding
(328 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-12340-0_19
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Matching cuts in graphs of high girth and H-free graphs
(2023)
Presentation / Conference Contribution
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search