About: We introduce and study a generalization of the well-known Steiner tree problem to count matroids. In the count matroid [Formula: see text], defined on the edge set of a graph [Formula: see text], a set [Formula: see text] is independent if every vertex set [Formula: see text] spans at most [Formula: see text] edges of F. The graph is called (k, l)-tight if its edge set is independent in [Formula: see text] and [Formula: see text] holds. Given a graph [Formula: see text], a non-negative length function [Formula: see text], a set [Formula: see text] of terminals and parameters k, l, our goal is to find a shortest (k, l)-tight subgraph of G that contains the terminals. Since [Formula: see text] is isomorphic to the graphic matroid of G, the special case [Formula: see text] corresponds to the Steiner tree problem. We obtain other interesting problems by choosing different parameters: for example, in the case [Formula: see text], [Formula: see text] the target is a shortest rigid subgraph containing all terminals. First we show that this problem is NP-hard even if [Formula: see text], [Formula: see text], and w is metric, or [Formula: see text] and [Formula: see text]. As a by-product of this result we obtain that finding a shortest circuit in [Formula: see text] is NP-hard. Then we design a [Formula: see text]-approximation algorithm for the metric version of the problem with parameters [Formula: see text], for all [Formula: see text]. In particular, we obtain a 3-approximation algorithm for the Steiner version of the shortest rigid subgraph problem. We also show that the metric version can be solved in polynomial time for [Formula: see text], [Formula: see text], provided |T| is fixed.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • We introduce and study a generalization of the well-known Steiner tree problem to count matroids. In the count matroid [Formula: see text], defined on the edge set of a graph [Formula: see text], a set [Formula: see text] is independent if every vertex set [Formula: see text] spans at most [Formula: see text] edges of F. The graph is called (k, l)-tight if its edge set is independent in [Formula: see text] and [Formula: see text] holds. Given a graph [Formula: see text], a non-negative length function [Formula: see text], a set [Formula: see text] of terminals and parameters k, l, our goal is to find a shortest (k, l)-tight subgraph of G that contains the terminals. Since [Formula: see text] is isomorphic to the graphic matroid of G, the special case [Formula: see text] corresponds to the Steiner tree problem. We obtain other interesting problems by choosing different parameters: for example, in the case [Formula: see text], [Formula: see text] the target is a shortest rigid subgraph containing all terminals. First we show that this problem is NP-hard even if [Formula: see text], [Formula: see text], and w is metric, or [Formula: see text] and [Formula: see text]. As a by-product of this result we obtain that finding a shortest circuit in [Formula: see text] is NP-hard. Then we design a [Formula: see text]-approximation algorithm for the metric version of the problem with parameters [Formula: see text], for all [Formula: see text]. In particular, we obtain a 3-approximation algorithm for the Steiner version of the shortest rigid subgraph problem. We also show that the metric version can be solved in polynomial time for [Formula: see text], [Formula: see text], provided |T| is fixed.
Subject
  • Graph theory
  • Closure operators
  • Computational problems in graph theory
  • NP-complete problems
  • Geometric algorithms
  • Geometric graphs
  • Trees (graph theory)
  • Glossaries of mathematics
  • Matroid theory
  • Set families
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
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-2024 OpenLink Software