Results 21 to 30 of about 2,587 (156)
On the Path-Width of Integer Linear Programming [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it.
Constantin Enea +3 more
doaj +1 more source
Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth [PDF]
ACM Journal of Experimental Algorithmics, 2016 Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical and practical interest.
Coudert, David +2 more
openaire +2 more sources
Linear Datalog and Bounded Path Duality of Relational Structures [PDF]
Logical Methods in Computer Science, 2005 In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs.
Victor Dalmau
doaj +1 more source
Exclusive graph searching vs. pathwidth
Information and Computation, 2016 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ευριπίδης Μάρκου +2 more
openalex +4 more sources
Pathwidth, trees, and random embeddings [PDF]
Combinatorica, 2013 We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair states that for every minor-closed family of graphs $F$, there is a constant $c(F)$ such that the ...
Lee, James R., Sidiropoulos, Anastasios
openaire +3 more sources
2-connecting Outerplanar Graphs without Blowing Up the Pathwidth [PDF]
Theoretical Computer Science, 2012 Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl, in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on
Jasine Babu +3 more
openalex +4 more sources
The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time.
Felix Canavoi +2 more
doaj +1 more source
EPG-representations with small grid-size [PDF]
, 2017 In an EPG-representation of a graph $G$ each vertex is represented by a path in the rectangular grid, and $(v,w)$ is an edge in $G$ if and only if the paths representing $v$ an $w$ share a grid-edge. Requiring paths representing edges to be x-monotone or,
A Asinowski +11 more
core +2 more sources
On edge-intersection graphs of k-bend paths in grids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2010 Edge-intersection graphs of paths in grids are graphs that can be represented such that vertices are paths in a grid and edges between vertices of the graph exist whenever two grid paths share a grid edge. This type of graphs is motivated by applications
Therese Biedl, Michal Stern
doaj +1 more source
FPT is Characterized by Useful Obstruction Sets [PDF]
, 2013 Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable, obstruction sets and efficient order tests is not just one way of ...
Fellows, Michael R., Jansen, Bart M. P.
core +1 more source