HOPS web view

This page lists:


Parameters

This browser does not support PDFs. Please download the PDF to view it: Download PDF.


All parameters in HOPS

Parameter*Relevance
acyclic chromatic number█████░░░░
arboricity█████░░░░
average degree██░░░░░░░
average distance███░░░░░░
bandwidth█████░░░░
bipartite number██░░░░░░░
bisection bandwidth████░░░░░
book thickness████░░░░░
boolean width█████░░░░
bounded components███░░░░░░
boxicity██████░░░
branch width█████░░░░
c-closure░░░░░░░░░
carving-width███░░░░░░
chordality████░░░░░
chromatic number█████░░░░
clique cover number█████░░░░
clique-tree-width██░░░░░░░
clique-width███████░░
contraction complexity██░░░░░░░
cutwidth████░░░░░
d-path-free██░░░░░░░
degeneracy██████░░░
degree treewidth██████░░░
diameter██████░░░
diameter+max degree░░░░░░░░░
distance to bipartite██████░░░
distance to block████░░░░░
distance to bounded components████░░░░░
distance to chordal████░░░░░
distance to cluster█████░░░░
distance to co-cluster█████░░░░
distance to cograph█████░░░░
distance to complete██████░░░
distance to disconnected░░░░░░░░░
distance to edgeless█░░░░░░░░
distance to forest█████░░░░
distance to interval███░░░░░░
distance to linear forest████░░░░░
distance to maximum degree████░░░░░
distance to outerplanar███░░░░░░
distance to perfect████░░░░░
distance to planar████░░░░░
distance to stars███░░░░░░
domatic number███░░░░░░
domination number███░░░░░░
edge clique cover number████░░░░░
edge connectivity██░░░░░░░
feedback edge set██████░░░
feedback vertex set████████░
genus██░░░░░░░
girth█░░░░░░░░
h-index████░░░░░
inf-flip-width███░░░░░░
iterated type partitions███░░░░░░
linear clique-width█████░░░░
linear NLC-width██░░░░░░░
linear rank-width██░░░░░░░
maximum clique█████░░░░
maximum degree████████░
maximum independent set██░░░░░░░
maximum induced matching███░░░░░░
maximum leaf number██████░░░
maximum matching███░░░░░░
maximum matching on bipartite graphs░░░░░░░░░
mim-width██████░░░
minimum degree░░░░░░░░░
mm-width████░░░░░
modular-width███████░░
module-width██████░░░
neighborhood diversity██████░░░
NLC-width████░░░░░
NLCT-width██░░░░░░░
odd cycle transversal██████░░░
pathwidth████████░
pathwidth+maxdegree███░░░░░░
radius-r flip-width███░░░░░░
rank-width███████░░
shrub-depth██████░░░
sim-width█████░░░░
size███░░░░░░
topological bandwidth████░░░░░
tree-independence number█████░░░░
treedepth███████░░
treelength██████░░░
treewidth█████████
twin-cover number█████░░░░
twin-width████████░
vertex connectivity░░░░░░░░░
vertex cover█████████
vertex integrity██████░░░

Graph classes

Some parameters are derived from associated graph classes. Graph classes can be also used as witnesses of proper inclusions. For these purposes, we use the following graph class hierarchy. We assume that all of the graph class inclusions are proper.

We aim to have here only the graph classes that influence parameter inclusions. Please, see Information System on Graph Classes and their Inclusions (ISGCI) for an exhaustive list of graph classes and their inclusions.

Graph class*Relevance
bipartite████████░
block████░░░░░
chordal█████░░░░
cluster██████░░░
co-cluster██████░░░
cograph███████░░
complete█████████
connected██░░░░░░░
cycle██░░░░░░░
cycles████░░░░░
disconnected░░░░░░░░░
disjoint cycles████░░░░░
edgeless█░░░░░░░░
forest█████████
grid██████░░░
interval███████░░
linear forest████░░░░░
outerplanar█████░░░░
path███░░░░░░
perfect██████░░░
planar████████░
star███░░░░░░
stars████░░░░░
tree███████░░

Sources

#Year*RelevanceSource
0002024███░░░░░░Parameterized complexity for iterated type partitions and modular-width by Cordasco, Gargano, Rescigno
0012024██░░░░░░░Twin-width of graphs on surfaces by Kráľ, Pekárková, Štorgel
0022023█░░░░░░░░On Algorithmic Applications of Sim-Width and Mim-Width of $(H_1,H_2)$-Free Graphs by Munaro, Yang
0032023███████░░Flip-width: Cops and Robber on dense graphs by Toruńczyk
0042022███████░░Expanding the Graph Parameter Hierarchy by Tran
0052021██████░░░Twin-width I: Tractable FO Model Checking by Bonnet, Kim, Thomassé, Watrigant
006unknown███████░░Comparing Graph Parameters by Schröder
0072020█░░░░░░░░Mim-Width I. Induced path problems by Jaffke, Kwon, Telle
0082019███████░░The Graph Parameter Hierarchy by Sorge
0092019█████░░░░Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Mendez
0102018█░░░░░░░░A systematic comparison of graph parameters by Frömmrich
0112017███████░░Graph Theory by Diestel
0122015█████████Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh
0132015████░░░░░Improving Vertex Cover as a Graph Parameter by Ganian
0142015██░░░░░░░Linear rank-width and linear clique-width of trees by Adler, Kanté
0152013█░░░░░░░░The Power of Data Reduction: Kernels for Fundamental Graph Problems by Jansen
0162013█░░░░░░░░Characterizing graphs of small carving-width by Belmonte, van ’t Hof, Kamiński, Paulusma, Thilikos
0172013███░░░░░░Parameterized Algorithms for Modular-Width by Gajarský, Lampis, Ordyniak
0182012███░░░░░░New Width Parameters of Graphs by Vatshelle
0192012████░░░░░Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
0202012█░░░░░░░░Algorithmic Meta-theorems for Restrictions of Treewidth by Lampis
0212011████░░░░░Boolean-width of graphs by Bui-Xuan, Telle, Vatshelle
0222011██░░░░░░░Chordal Bipartite Graphs with High Boxicity by Chandran, Francis, Mathew
0232010███████░░Comparing 17 graph parameters by Sasák
0242010█░░░░░░░░The rank-width of the square grid by Jelínek
0252009██░░░░░░░Clique-Width is NP-Complete by Fellows, Rosamond, Rotics, Szeider
0262008███░░░░░░Grad and classes with bounded expansion II. Algorithmic aspects by Nešetřil, Ossona de Mendez
0272008██░░░░░░░Spanning Trees with Many Leaves and Average Distance by DeLaViña, Waller
0282008██░░░░░░░Simulating Quantum Computation by Contracting Tensor Networks by Markov, Shi
0292007████░░░░░Graph Treewidth and Geometric Thickness Parameters by Dujmovic, Wood
0302006████░░░░░Approximating clique-width and branch-width by Oum, Seymour
0312005███░░░░░░On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
0322004███░░░░░░Track Layouts of Graphs by Dujmović, Pór, Wood
0332000█████░░░░Upper bounds to the clique width of graphs by Courcelle, Olariu
0341998███░░░░░░Clique-decomposition, NLC-decomposition and modular decomposition—relationships and results for random graphs by Johansson
0351998██████░░░A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
0361994███░░░░░░k-NLC graphs and polynomial algorithms by Wanke
0371993█████░░░░The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
0381991███████░░Graph minors. X. Obstructions to tree-decomposition by Robertson, Seymour
0391986███░░░░░░Graph minors. V. Excluding a planar graph by Robertson, Seymour
0401994██░░░░░░░Genus g Graphs Have Pagenumber O(√g) by Malitz
0411993████░░░░░On the chordality of a graph by McKee, Scheinerman
0421986████████░Graph minors. II. Algorithmic aspects of tree-width by Robertson, Seymour
0431988█░░░░░░░░The average distanceisnot morethan the independence number by Chung
0441985█░░░░░░░░On the Cutwidth and the Topological Bandwidth of a Tree by Chung

Tags