37 citations · 64 across the 8 of their papers we have counts for
8 papers
Boxicity and Interval-Orders: Petersen and the Complements of Line Graphs
Marco Caoduro, András Sebő
The boxicity of a graph is the smallest dimension allowing a representation of it as the intersection graph of a set of -dimensional axis-parallel boxes. We present a simple…
Odd Paths, Cycles and -joins: Connections and Algorithms
Ildikó Schlotter, András Sebő
Minimizing the weight of an edge set satisfying parity constraints is a challenging branch of combinatorial optimization as witnessed by the binary hypergraph chapter of Alexander…
Packing, Hitting, and Colouring Squares
Marco Caoduro, András Sebő
Given a finite family of squares in the plane, the packing problem asks for the maximum number of pairwise disjoint squares among them, while the hitting problem for the minimu…
The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio
András Sebő, Anke van Zuylen
We give a new, strongly polynomial-time algorithm and improved analysis for the metric path TSP. It finds a tour of cost less than 1.53 times the optimum of the subtour elimi…
Ear-decompositions and the complexity of the matching polytope
Yohann Benchetrit, András Sebő
The complexity of the matching polytope of graphs may be measured with the maximum length of a starting sequence of odd ears in an ear-decomposition. Indeed, a theorem of Edmon…
Complements of nearly perfect graphs
András Gyárfás, Zhentao Li, Raphael Machado +3
A class of graphs closed under taking induced subgraphs is -bounded if there exists a function such that for all graphs in the class, . We consider th…