About: Further Results on Online Node- and Edge-Deletion Problems with Advice

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

About: Further Results on Online Node- and Edge-Deletion Problems with Advice Goto Sponge NotDistinct Permalink

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

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Further Results on Online Node- and Edge-Deletion Problems with Advice
Creator	Chen, Li-Hsuan Hung, Ling-Ju Lotze, Henri Rossmanith, Peter
Source	PMC
abstract	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.
has issue date	2020-04-30(xsd:dateTime)
bibo:doi	10.1007/978-3-030-48966-3_11
has license	no-cc
sha1sum (hex)	5a7d0ecf88f77b54c4fddba998511324e7894943
schema:url	https://doi.org/10.1007/978-3-030-48966-3_11
resource representing a document's title	Further Results on Online Node- and Edge-Deletion Problems with Advice
has PubMed Central identifier	PMC7254923
schema:publication	Combinatorial Algorithms
resource representing a document's body	covid:5a7d0ecf88f77b54c4fddba998511324e7894943#body_text
is schema:about of	named entity 'order' named entity 'forbidden' named entity 'connected' named entity 'nodes' named entity 'NODE' named entity 'easy' named entity 'problems' named entity 'disconnected' named entity 'advice' named entity 'node' named entity 'induced' named entity 'solution' named entity 'algorithm' named entity 'graph' named entity 'online algorithm' named entity 'lexicographically' named entity 'minimization problem' named entity 'algorithm' named entity 'characteristic polynomial' named entity 'G i' named entity 'algorithm' named entity 'Hromkovič' named entity 'subgraph' named entity 'algorithm' named entity 'graph' named entity 'graph' named entity 'Algorithm' named entity 'Cmax' named entity 'forbidden induced subgraph' named entity 'lower bound' named entity 'optimal solution' named entity 'online algorithm' named entity 'deterministic' named entity 'graph' named entity 'algorithm' named entity 'iff' named entity 'algorithm' named entity 'vertex cover' named entity 'graph' named entity 'algorithm' named entity 'upper and lower bounds' named entity 'algorithm' named entity 'competitive ratio' named entity 'graph' named entity 'algorithm' named entity 'induced matching' named entity 'k-server problem' named entity 'graph' named entity 'algorithm' named entity 'subset' named entity 'algorithm' named entity 'arg max' named entity 'graph' named entity 'decision model' named entity 'k-Server Problem' named entity 'algorithm' named entity 'isomorphism' named entity 'Descartes' rule of signs' named entity 'competitive ratio' named entity 'deterministic algorithm' named entity 'induced subgraph' named entity 'online algorithm' named entity 'algorithm' named entity 'recurrence relation' named entity 'binary representation' named entity 'algorithm' named entity 'Vertex Cover' named entity 'subset' named entity 'C max' named entity 'algorithm' named entity 'competitive ratio' named entity 'graph' named entity 'competitive ratio' named entity 'lower bounds' named entity 'C max' named entity 'finite set' named entity 'subset' named entity 'induced subgraphs' named entity 'connected graph' named entity 'optimal solution'

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-2024 OpenLink Software