English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2014). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. Retrieved from http://arxiv.org/abs/1403.0789.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-4060-9 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0025-0035-E
Genre: Paper

Files

show Files
hide Files
:
arXiv:1403.0789.pdf (Preprint), 211KB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0024-4062-5
Name:
arXiv:1403.0789.pdf
Description:
File downloaded from arXiv at 2014-11-26 08:47
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/help/license

Locators

show

Creators

show
hide
 Creators:
Golovach, Petr A., Author
Paulusma, Daniël, Author
van Leeuwen, Erik Jan1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We present a linear-time algorithm for Induced Disjoint Paths on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not necessarily distinct.

Details

show
hide
Language(s): eng - English
 Dates: 2014-03-042014-03-04
 Publication Status: Published online
 Pages: 18 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1403.0789
URI: http://arxiv.org/abs/1403.0789
BibTex Citekey: DBLP:journals/corr/GolovachPL14
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show