WG B

35 papers

YearTitle / Authors
2014A Characterization of Mixed Unit Interval Graphs.
Felix Joos
2014A New Characterization of P
Eglantine Camby, Oliver Schaudt
2014A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs.
Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
2014Between Treewidth and Clique-Width.
Sigve Hortemo Sæther, Jan Arne Telle
2014Boxicity and Separation Dimension.
Manu Basavaraju, L. Sunil Chandran, Martin Charles Golumbic, Rogers Mathew, Deepak Rajendraprasad
2014Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs.
Michel Habib, Antoine Mamcarz
2014Contact Representations of Planar Graphs: Extending a Partial Representation is Hard.
Steven Chaplick, Paul Dorbec, Jan Kratochvíl, Mickaël Montassier, Juraj Stacho
2014DMVP: Foremost Waypoint Coverage of Time-Varying Graphs.
Eric Aaron, Danny Krizanc, Elliot Meyerson
2014Deciding the Bell Number for Hereditary Graph Properties - (Extended Abstract).
Aistis Atminas, Andrew Collins, Jan Foniok, Vadim V. Lozin
2014Distributedly Testing Cycle-Freeness.
Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, Fabien Mathieu
2014Edge Elimination in TSP Instances.
Stefan Hougardy, Rasmus T. Schroeder
2014Graph-TSP from Steiner Cycles.
Satoru Iwata, Alantha Newman, R. Ravi
2014Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
Dieter Kratsch, Ioan Todinca
2014Hadwiger Number of Graphs with Small Chordality.
Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Christophe Paul
2014Independent Set Reconfiguration in Cographs.
Paul S. Bonsma
2014Induced Disjoint Paths in Circular-Arc Graphs in Linear Time.
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
2014Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees.
Leo van Iersel, Steven Kelk
2014Linear Rank-Width of Distance-Hereditary Graphs.
Isolde Adler, Mamadou Moustapha Kanté, O-joung Kwon
2014Maximal Induced Matchings in Triangle-Free Graphs.
Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, Yngve Villanger
2014Minimum Spanning Tree Verification Under Uncertainty.
Thomas Erlebach, Michael Hoffmann
2014Near-Linear Time Constant-Factor Approximation Algorithm for Branch-Decomposition of Planar Graphs.
Qian-Ping Gu, Gengchun Xu
2014On Set Expansion Problems and the Small Set Expansion Conjecture.
Rajiv Gandhi, Guy Kortsarz
2014On the Number of Connected Sets in Bounded Degree Graphs.
Kustaa Kangas, Petteri Kaski, Mikko Koivisto, Janne H. Korhonen
2014Parameterized Algorithms for Graph Partitioning Problems.
Hadas Shachnai, Meirav Zehavi
2014Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs.
Gregory Z. Gutin, Mark Jones, Bin Sheng, Magnus Wahlström
2014Parameterized Edge Hamiltonicity.
Michael Lampis, Kazuhisa Makino, Valia Mitsou, Yushi Uno
2014Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs.
Van Bang Le, Andrea Oversberg, Oliver Schaudt
2014Recognizing Threshold Tolerance Graphs in O(n
Petr A. Golovach, Pinar Heggernes, Nathan Lindzey, Ross M. McConnell, Vinícius Fernandes dos Santos, Jeremy P. Spinrad
2014Structural Parameterizations for Boxicity.
Henning Bruhn, Morgan Chopin, Felix Joos, Oliver Schaudt
2014The Maximum Labeled Path Problem.
Basile Couëtoux, Elie Nakache, Yann Vaxès
2014The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results.
Thiago Braga Marcilon, Samuel Nascimento, Rudini M. Sampaio
2014The Parameterized Complexity of the Rainbow Subgraph Problem.
Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Martin Rötzschke
2014Towards the Hanani-Tutte Theorem for Clustered Graphs.
Radoslav Fulek
2014Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract).
Reinhard Diestel, Sang-il Oum
2014Vertex Contact Graphs of Paths on a Grid.
Nieke Aerts, Stefan Felsner