About: In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class at all times. We consider graph classes that can be characterized by forbidden sets of induced subgraphs and analyze the advice complexity of getting an optimal solution. We give almost tight lower and upper bounds for the [Image: see text] , where there is one forbidden induced subgraph that may or may not be disconnected and tight bounds on the [Image: see text] , where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from [Formula: see text]. For the [Image: see text] the advice complexity is basically an easy function of the size of the biggest component in H.   Goto Sponge  NotDistinct  Permalink

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

AttributesValues
type
value
  • In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class at all times. We consider graph classes that can be characterized by forbidden sets of induced subgraphs and analyze the advice complexity of getting an optimal solution. We give almost tight lower and upper bounds for the [Image: see text] , where there is one forbidden induced subgraph that may or may not be disconnected and tight bounds on the [Image: see text] , where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from [Formula: see text]. For the [Image: see text] the advice complexity is basically an easy function of the size of the biggest component in H.
Subject
  • Algorithms
  • Graph theory
  • Mathematical logic
  • Theoretical computer science
  • Order theory
  • Graph minor theory
  • Free will
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