About: Parameterized Complexity of [Formula: see text]-Path Packing

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Parameterized Complexity of [Formula: see text]-Path Packing Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Parameterized Complexity of [Formula: see text]-Path Packing
Creator	Kobayashi, Yusuke Belmonte, Rémy Hanaka, Tesshu Kanzaki, Masaaki Kiyomi, Masashi Kobayashi, Yasuaki Lampis, Michael Ono, Hirotaka Otachi, Yota
source	PMC
abstract	Given a graph [Formula: see text], [Formula: see text], and integers k and [Formula: see text], the [Formula: see text] -Path Packing problem asks to find k vertex-disjoint paths of length [Formula: see text] that have endpoints in A and internal points in [Formula: see text]. We study the parameterized complexity of this problem with parameters \|A\|, [Formula: see text], k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when [Formula: see text], while it is NP-complete for constant [Formula: see text]. We also show that the problem is W[1]-hard parameterized by pathwidth[Formula: see text], while it is fixed-parameter tractable parameterized by treewidth[Formula: see text].
has issue date	2020-04-30(xsd:dateTime)
bibo:doi	10.1007/978-3-030-48966-3_4
has license	no-cc
sha1sum (hex)	4a00030943a8a861dc884af37fcbfc6f775a5950
schema:url	https://doi.org/10.1007/978-3-030-48966-3_4
resource representing a document's title	Parameterized Complexity of [Formula: see text]-Path Packing
has PubMed Central identifier	PMC7254919
schema:publication	Combinatorial Algorithms
resource representing a document's body	covid:4a00030943a8a861dc884af37fcbfc6f775a5950#body_text
is schema:about of	named entity 'integers' named entity 'solvable' named entity 'CONSTANT' named entity 'COMPLEXITY' named entity 'COMPLETE' covid:arg/4a00030943a8a861dc884af37fcbfc6f775a5950 named entity 'treewidth' named entity 'ALPP' named entity 'Hamiltonian Cycle' named entity 'efficient algorithm' named entity 'pathwidth' named entity 'constant' named entity 'treewidth' named entity 'treewidth' named entity 'NP-complete' named entity 'vertex-disjoint paths' named entity 'pathwidth' named entity 'Packing problem' named entity 'ALPP' named entity 'vertex' named entity 'vertex' named entity 'MCC' named entity 'vertices' named entity 'FPT' named entity 'vertices' named entity 'subgraph' named entity 'treewidth' named entity 'vertices' named entity 'graph' named entity 'algorithm' named entity 'vertices' named entity 'tree decomposition' named entity 'vertices' named entity 'algorithm' named entity 'graph' named entity 'pathwidth' named entity 'efficient algorithms' named entity 'vertex' named entity 'disjoint' named entity 'Maximum Matching' named entity 'ALPP' named entity 'subgraph' named entity 'monadic second-order logic' named entity 'maximum matching' named entity 'ALPP' named entity '5.1' named entity 'cw +' named entity 'isomorphic' named entity 'graph' named entity 'maximum matching' named entity 'graph' named entity 'bipartite' named entity 'polynomial' named entity 'vertices' named entity 'vertices' named entity 'vertices' named entity 'parameterized complexity theory' named entity 'NP-complete' named entity 'vertex' named entity 'graph' named entity 'treewidth' named entity 'clique-width' named entity 'disjoint' named entity 'graph' named entity 'vertex' named entity 'graph' named entity 'triples' named entity 'disjoint' named entity 'vertex' named entity 'connected components' named entity 'graph problem' named entity 'pathwidth' named entity 'polynomial-time' named entity 'triples' named entity 'vertex'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software