Attributes | Values |
---|
rdf:type
| |
rdfs:seeAlso
| |
Description
| - The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s (i) ,t (i) ) for i=1,aEuro broken vertical bar,k and is to test whether G contain k mutually induced paths P (i) such that P (i) connects s (i) and t (i) for i=1,aEuro broken vertical bar,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.
- The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s (i) ,t (i) ) for i=1,aEuro broken vertical bar,k and is to test whether G contain k mutually induced paths P (i) such that P (i) connects s (i) and t (i) for i=1,aEuro broken vertical bar,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs. (en)
|
Title
| - The k-in-a-Path Problem for Claw-free Graphs
- The k-in-a-Path Problem for Claw-free Graphs (en)
|
skos:prefLabel
| - The k-in-a-Path Problem for Claw-free Graphs
- The k-in-a-Path Problem for Claw-free Graphs (en)
|
skos:notation
| - RIV/00216208:11320/12:10125750!RIV13-GA0-11320___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(1M0545), P(GA201/09/0197)
|
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/12:10125750
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - Polynomial time algorithm; Claw-free graph; Induced path (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| - DE - Spolková republika Německo
|
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| |
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Fiala, Jiří
- Lidický, Bernard
- Kaminski, Marcin
- Paulusma, Daniel
|
http://linked.open...ain/vavai/riv/wos
| |
issn
| |
number of pages
| |
http://bibframe.org/vocab/doi
| - 10.1007/s00453-010-9468-z
|
http://localhost/t...ganizacniJednotka
| |