About: Computability of Width of Submodular Partition Functions     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

AttributesValues
rdf:type
Description
  • The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k, there are polynomial-time algorithms to determine whether a graph has tree-width, branch-width, etc. at most k. Contrary to these results, we show that there is no sub-exponential algorithm for determining whether the width of a given submodular partition function is at most two. In addition, we also develop another dual notion for submodular partition functions which is analogous to loose tangles for connectivity functions.
  • The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k, there are polynomial-time algorithms to determine whether a graph has tree-width, branch-width, etc. at most k. Contrary to these results, we show that there is no sub-exponential algorithm for determining whether the width of a given submodular partition function is at most two. In addition, we also develop another dual notion for submodular partition functions which is analogous to loose tangles for connectivity functions. (en)
Title
  • Computability of Width of Submodular Partition Functions
  • Computability of Width of Submodular Partition Functions (en)
skos:prefLabel
  • Computability of Width of Submodular Partition Functions
  • Computability of Width of Submodular Partition Functions (en)
skos:notation
  • RIV/00216208:11320/09:10031828!RIV11-GA0-11320___
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • P(1M0545), P(GA201/09/0197), Z(MSM0021620838)
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
  • 307925
http://linked.open...ai/riv/idVysledku
  • RIV/00216208:11320/09:10031828
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • width parameters; partition submodular functions (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...ontrolniKodProRIV
  • [7509B7B1D1F8]
http://linked.open...v/mistoKonaniAkce
  • Hradec nad Moravicí
http://linked.open...i/riv/mistoVydani
  • Berlin
http://linked.open...i/riv/nazevZdroje
  • Combinatorial Algorithms
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...iv/tvurceVysledku
  • Škoda, Petr
http://linked.open...vavai/riv/typAkce
http://linked.open...ain/vavai/riv/wos
  • 000280084100043
http://linked.open.../riv/zahajeniAkce
http://linked.open...n/vavai/riv/zamer
number of pages
http://purl.org/ne...btex#hasPublisher
  • Springer-Verlag
https://schema.org/isbn
  • 978-3-642-10216-5
http://localhost/t...ganizacniJednotka
  • 11320
is http://linked.open...avai/riv/vysledek of
Faceted Search & Find service v1.16.116 as of Feb 22 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3239 as of Feb 22 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 82 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software