Graph Layout Problems Parameterized by Vertex Cover

DOI10.1007/978-3-540-92182-0_28zbMath1183.68424OpenAlexW1485295947WikidataQ57359887 ScholiaQ57359887MaRDI QIDQ3596727

Neeldhara Misra, Frances A. Rosamond, Daniel Lokshtanov, Saket Saurabh, Michael R. Fellows

Publication date: 29 January 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: http://espace.cdu.edu.au/view/cdu:9602

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Iterated Type Partitions, On Cutwidth Parameterized by Vertex Cover, Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics, Parameterized complexity of locally minimal defensive alliances, Safe sets in graphs: graph classes and structural parameters, Graph isomorphism parameterized by elimination distance to bounded degree, Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number, On the harmless set problem parameterized by treewidth, Kernelization using structural parameters on sparse graph classes, Treewidth and pathwidth parameterized by the vertex cover number, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, Algorithmic Applications of Tree-Cut Width, Two-layer planarization parameterized by feedback edge set, FPT algorithms to compute the elimination distance to bipartite graphs and more, Integer programming in parameterized complexity: five miniatures, Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts, An algorithmic framework for locally constrained homomorphisms, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Parameterized complexity of envy-free resource allocation in social networks, Approximation and parameterized algorithms for balanced connected partition problems, Safe Sets in Graphs: Graph Classes and Structural Parameters, Parameterized complexity for iterated type partitions and modular-width, Structural parameterization of alliance problems, Polynomial-time data reduction for weighted problems beyond additive goal functions, Balanced connected partitions of graphs: approximation, parameterization and lower bounds, Extended MSO model checking via small vertex integrity, Small vertex cover makes Petri net coverability and boundedness easier, Parameterized Complexity of Safe Set, Combinatorial \(n\)-fold integer programming and applications, Parameterized algorithms for book embedding problems, Group activity selection with few agent types, Maximum common induced subgraph parameterized by vertex cover, On structural parameterizations of the bounded-degree vertex deletion problem, On cutwidth parameterized by vertex cover, Parameterized Algorithms for Book Embedding Problems, Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, The Small Set Vertex expansion problem, The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, The complexity landscape of decompositional parameters for ILP, Swapping colored tokens on graphs, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Parameterized complexity of asynchronous border minimization, Parameterizing by the number of numbers, Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Algorithmic meta-theorems for restrictions of treewidth, Parameterized complexity of coloring problems: treewidth versus vertex cover, Unnamed Item, Finding vertex-surjective graph homomorphisms, Alliances in graphs of bounded clique-width, On structural parameterizations of the edge disjoint paths problem, The complexity ecology of parameters: An illustration using bounded max leaf number, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, Imbalance parameterized by twin cover revisited, Exploring the gap between treedepth and vertex cover through vertex integrity, Using decomposition-parameters for QBF: mind the prefix!, Parameterized Complexity Results for 1-safe Petri Nets, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., On bounded-degree vertex deletion parameterized by treewidth, Algorithmic Applications of Tree-Cut Width, Offensive alliances in graphs, Critical elements in combinatorially closed families of graph classes